{"id":"4439c679-982e-44ab-87b6-9440c6185286","arxiv_id":"2412.16802","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Balls-and-Bins sampling for DP-SGD has a tight privacy analysis: as private as Poisson at large epsilon, with shuffle-comparable utility, verified by Monte Carlo accounting.","lead":"Researchers introduce Balls-and-Bins sampling for DP-SGD, which places each training example in one random batch, and derive a tight privacy analysis for it. The method combines the easy implementation and utility of shuffling with privacy guarantees comparable to Poisson subsampling, closing a known gap between how DP-SGD is run and how its privacy is accounted.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.1 is sound, but the practical 'best-of-both' claim is not established: δB ≤ δP is proven only asymptotically, and the Monte Carlo evidence is inconclusive exactly when δP < 1e-7; multi-epoch is only sketched.","rationale":"I read the paper in good faith and the main theoretical contribution checks out: Theorem 3.1's dominating pair is derived carefully, the post-processing argument for the upper bound is sound, and the order-statistics and importance-sampling estimators are legitimate high-probability upper-bound tools. The concern is not an internal inconsistency in Theorem 3.1 but a mismatch between what is proven and what the abstract claims. To support 'similar-or-better privacy amplification as compared to Poisson in practical regimes', the paper needs δB(ε) ≤ δP(ε) at the finite ε values used in practice. Theorem 3.4 only gives an asymptotic statement with an unspecified threshold, and the paper's own Remark 3.5 leaves open the possibility of finite-ε regimes where δB exceeds δP. The Monte Carlo upper bounds in Figure 2 are the only evidence for finite ε, and the paper itself reports that they are inconclusive when δP < 1e-7. Since δ ≈ 1e-6 or smaller is a common practical privacy target, this is precisely the regime that matters. The multi-epoch extension is also presented as a direction rather than a validated result: Appendix B.4 gives an estimator but no importance sampler and no experiments, even though multi-epoch training is standard in DP-SGD deployments. These are concrete, addressable gaps rather than fatal flaws, so the correct disposition is the reader's CONDITIONAL verdict. I would keep that verdict unchanged and ask the authors to either prove or carefully qualify the low-δ and multi-epoch parts of the practical claim.","tokens_in":22400,"tokens_out":14586,"duration_ms":135629,"concrete_test":"Use the certified non-asymptotic bound from Feldman and Shenfeld (2025), already cited in the paper's Discussion, to upper-bound δB(ε) for the exact Figure 2 configurations whose Monte Carlo comparison to δP was inconclusive (the panels with δP < 1e-7), and compare this certified bound to δP(ε). If the certified bound is below δP(ε), the low-δ gap is closed; if it is above or cannot be computed, the paper's central 'similar-or-better than Poisson' claim is not established in the regime that motivated it.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The theoretical core, Theorem 3.1, gives a tightly dominating pair (PB, QB) for ABLQ_B, and the proof via conditioning on placements of the other examples plus joint convexity appears sound; I find no internal error there. The load-bearing gap is in the practical claim that Balls-and-Bins is no less private than Poisson in regimes where DP-SGD is actually used. Theorem 3.4 proves δB(ε) < δP(ε) only for all sufficiently large ε, with no quantitative bound on the threshold ε0. Remark 3.5 and Theorem D.1 show the pairs are incomparable and explicitly leave open whether δB(ε) > δP(ε) for any ε ≥ 0. The experiments therefore carry the weight, but Figure 2 reports upper confidence bounds on δB, not deterministic guarantees, and the caption concedes these bounds are not tight enough to separate δB from δP when δP < 1e-7, where the authors say only that they 'believe' δB < δP. Appendix B.4 extends estimation to multiple epochs with naive Monte Carlo only, explicitly dropping importance sampling and offering no experiments, so the multi-epoch DP-SGD setting is unvalidated. Thus the recommendation to adopt Balls-and-Bins as a drop-in replacement for Poisson rests on an unproven, and in the low-δ regime unverified, inequality.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces the Balls-and-Bins batch generator B, in which each example is assigned independently to a uniformly random batch. Its main theoretical result, Theorem 3.1, identifies a tightly dominating pair (P_B, Q_B) = ((1/T) Σ_t N(e_t, σ²I_T), N(0, σ²I_T)) for the adaptive-batch linear-query mechanism ABLQ_B, and the proof via conditioning on the placements of non-differing examples plus joint convexity of hockey-stick divergence appears sound. Building on this, Proposition 3.3 shows δ_B ≤ δ_S ≤ δ_D, and Theorem 3.4 shows δ_B < δ_P for all sufficiently large ε, while Remark 3.5 and Appendix D establish that the privacy guarantees of ABLQ_B and ABLQ_P are incomparable in general. The paper also develops Monte Carlo estimation for δ_B using importance sampling and a new order-statistics sampling technique, and reports single-epoch DP-SGD utility experiments on two Criteo datasets showing that B and S have comparable AUC, with privacy upper bounds for B below δ_P in most tested regimes. The authors explicitly acknowledge in Section 6 that a tight provable accounting for ABLQ_B is open and that multi-epoch training is only sketched in Appendix B.4.","tokens_in":22614,"tokens_out":7483,"duration_ms":63798,"significance":"The tightly dominating pair in Theorem 3.1 is a clean and checkable theoretical contribution: it gives an exact privacy characterization for a sampler whose per-example positions are independent and whose implementation is close to shuffling. The proof is elegant and, as far as I can check, correct. The order-statistics sampling technique is likely to be of independent interest for Monte Carlo privacy accounting of high-dimensional mechanisms, and the paper ships reproducible accounting code. The Monte Carlo upper bounds are valid as stated. However, the headline claim that Balls-and-Bins enjoys 'similar-or-better privacy amplification compared to Poisson subsampling in practical regimes' is not fully established: Theorem 3.4 is asymptotic, the Monte Carlo bounds are inconclusive at δ_P < 1e-7, and multi-epoch DP-SGD is not experimentally validated. The central theory is sound, but the applied 'best-of-both' claim needs additional support or more careful scoping.","major_comments":[{"comment":"The abstract's claim of 'similar-or-better privacy amplification as compared to Poisson subsampling in practical regimes' is not established for δ_P < 1e-7. The Monte Carlo upper confidence bounds in Figure 2 are valid, but the text concedes that they are not tight enough to separate δ_B from δ_P exactly in this region, and the authors state only 'We believe δ_B(ε) < δ_P(ε) even in this regime.' Since Theorem 3.4 proves δ_B < δ_P only for all sufficiently large ε and gives no quantitative threshold ε0, the paper does not currently prove the headline claim in the low-δ regime. I would like either a non-asymptotic analytical bound covering the practical δ region (for example by incorporating the Feldman-Shenfeld decomposition cited in the Discussion) or a revised claim in the abstract that limits 'similar-or-better' to the regimes where the Monte Carlo bounds are conclusive.","section":"Section 5, Figure 2; Section 6"},{"comment":"Multi-epoch privacy accounting is only sketched. Algorithm 11 uses naive Monte Carlo, the text explicitly says 'Importance sampling is not directly applicable,' and no privacy or utility experiments are given for k > 1. Because multi-epoch training is standard in DP-SGD deployments, the paper's framing of Balls-and-Bins as a drop-in replacement for shuffling is not validated beyond a single epoch. If the contribution is intended to be single-epoch, this limitation should be stated prominently in the introduction or abstract; if multiple epochs are claimed, the appendix needs supporting experiments or at least a discussion of how the order-statistics technique degrades with k.","section":"Appendix B.4"},{"comment":"The formal comparison between ABLQ_B and ABLQ_P is weaker than the text sometimes suggests. Theorem 3.4 proves only that δ_B(ε) < δ_P(ε) for all sufficiently large ε, while Remark 3.5 and Theorem D.1 show that the two pairs are incomparable and Appendix D explicitly leaves open whether δ_B(ε) > δ_P(ε) for any ε ≥ 0. The paper should state this precision whenever it claims 'no less private than Poisson' or 'similar-or-better privacy amplification,' rather than relying on the asymptotic theorem alone.","section":"Remark 3.5 and Appendix D"}],"minor_comments":[{"comment":"The phrase 'cumulative density function' should be 'cumulative distribution function' (or CDF) for consistency with standard terminology.","section":"Section 4, Algorithm 6; Appendix B"},{"comment":"In the pseudocode for the Balls-and-Bins sampler, the inner loop reuses the variable name t for both the outer batch index and the randomly chosen batch; this is confusing. Rename the chosen index (e.g., t_i) so the pseudocode is unambiguous.","section":"Algorithm 3"},{"comment":"The utility experiments are limited to two Criteo datasets, a single epoch, and three runs per setting, and the training code is not released (only the accounting code is). The paper would be clearer if the utility claim were explicitly scoped to these settings rather than stated as a general property of the sampler.","section":"Section 5 and Appendix C"}],"recommendation":"major_revision","confidential_remarks":"The theoretical core is strong and I found no internal error in Theorem 3.1. The gap is in the public 'best-of-both' claim, which is stronger than what is proved: the privacy comparison to Poisson is asymptotic or Monte-Carlo-based, with an acknowledged inconclusive low-δ region and only a sketch for multiple epochs. This is fixable either by incorporating the cited Feldman-Shenfeld non-asymptotic bounds or by softening the abstract and framing the paper as a single-epoch contribution. I would support acceptance after such a revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this paper deserves a serious referee. The core new result, Theorem 3.1, is a tightly dominating pair for the ABLQ_B mechanism, and the proof is honest and checkable. The order-statistics sampling technique is also a genuinely useful tool for Hochschild divergences in high-dimensional settings, likely independent of DP. The paper is transparent about its own limitations, which counts for a lot.\n\nWhat is actually new: the dominating pair (P_B, Q_B), the transfer of the large-epsilon comparison from ABLQ_D to ABLQ_B, and the Monte Carlo machinery (importance sampling plus order statistics) for estimating delta_B. The proof of Theorem 3.1 is a clean application of joint convexity and post-processing; I could not find a hole. The experiments show what they claim: Balls-and-Bins utility is close to Shuffle, and the Monte Carlo upper bounds sit below the Poisson curve in the plotted regimes. The paper also clearly credits prior work on random check-ins and notes the concurrent DP-FTRL analysis.\n\nThe soft spots are real but are mostly acknowledged by the authors. The headline claim \"similar-or-better privacy than Poisson\" is proven only asymptotically (Theorem 3.4), and Theorem D.1 leaves open the possibility that delta_B(eps) > delta_P(eps) for some eps. The Monte Carlo bounds are valid but loose when delta_P is below about 1e-7, which is exactly where the authors say they \"believe\" the inequality holds. So the practical recommendation to drop Balls-and-Bins in as a replacement for Poisson is not fully supported in the small-delta or multi-epoch regimes, and the multi-epoch extension (Appendix B.4) is explicitly naive Monte Carlo with no importance sampling and no experiments. That is a fair criticism, and the authors do not hide it. One minor but concrete issue: the GitHub link in the text looks like it has a space in the path (\"dpsgd batch sampler accounting\") and no commit hash; those are easily fixed.\n\nWho gets value: people who build DP-SGD libraries and want a shuffle-like sampler with an accounting method that is not as pessimistic as existing shuffle bounds. It is also a useful case study in how to do Monte Carlo privacy accounting when you cannot get a tractable deterministic bound. I would cite the dominating pair and the order-statistics estimator.\n\nThe right outcome is to send this to peer review. The central theoretical claim is solid, the limitations are stated, and the main open problems are load-bearing enough that a good referee can help sharpen the claims. I would recommend acceptance after the authors tighten the language around \"best-of-both\" and fix the reproducibility details.","headline":"A tight dominating pair for Balls-and-Bins DP-SGD is the real new result, and it is cleanly proven; the 'best-of-both' story is credible in single-epoch, common-parameter regimes, but the paper itself leaves the small-delta and multi-epoch gaps open.","tokens_in":23274,"tokens_out":2161,"would_cite":true,"duration_ms":20430,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper introduces Balls-and-Bins sampling for DP-SGD—each example lands in one uniformly random batch—and proves it keeps shuffle-like utility while matching or beating Poisson subsampling's privacy in practical regimes.","keywords":["differential privacy","DP-SGD","privacy amplification","shuffling","Poisson subsampling","hockey stick divergence","dominating pairs","Monte Carlo privacy accounting"],"falsifier":"Compute $\\delta_B(\\varepsilon)$ with a provably tight accountant---for instance the characteristic-function or privacy-loss-distribution method already used for Poisson---at the Figure 2 configurations where the Monte Carlo bounds were inconclusive, such as $T=4517$, $\\sigma=0.3$, $\\varepsilon$ near $10$ with $\\delta_P \\approx 10^{-8}$; if the exact $\\delta_B$ exceeds $\\delta_P$ there, the best-of-both claim fails in a practical regime.","tokens_in":22131,"feed_emoji":"🎲","tokens_out":11254,"duration_ms":80983,"temperature":0.7,"pith_summary":"Most differentially private training pipelines shuffle the data but report privacy as if they used Poisson subsampling, and recent work has shown that this gap can make the reported privacy much stronger than the real guarantee. This paper proposes Balls-and-Bins sampling, where each training example is assigned to exactly one uniformly random batch, an implementation as simple as shuffling that makes each batch's marginal distribution identical to Poisson subsampling. The central result is a tight privacy characterization: the privacy loss of the adaptive-batch linear-query mechanism under this sampler is exactly captured by the pair $(P_B, Q_B)$, which yields $\\delta_B(\\varepsilon) \\le \\delta_S(\\varepsilon) \\le \\delta_D(\\varepsilon)$ for all $\\varepsilon>0$ and $\\delta_B(\\varepsilon) < \\delta_P(\\varepsilon)$ for sufficiently large $\\varepsilon$. If the practical ordering holds as the Monte Carlo evidence suggests, practitioners can keep shuffle-like training and utility while claiming Poisson-grade privacy, without changing their DP-SGD code beyond the batch generator.","feed_headline":"Random-batch DP-SGD sampler matches shuffle utility, Poisson privacy","feed_subtitle":"Each example lands in one random batch, so DP-SGD keeps shuffle-style training with Poisson-like accounting.","key_machinery":"The load-bearing object is the tightly dominating pair $(P_B, Q_B)$: a pair of distributions whose $e^\\varepsilon$-hockey-stick divergence equals, at every $\\varepsilon$, the worst-case privacy loss of the adaptive-batch linear-query mechanism under Balls-and-Bins sampling. The proof that this pair dominates the mechanism averages over all possible batch assignments using joint convexity of the hockey-stick divergence, and shows the pair is attained by a specific adjacent pair of datasets, giving tightness. This reduces privacy accounting for Balls-and-Bins to computing two divergences between Gaussian mixtures, which the paper then estimates with Monte Carlo methods built on importance sampling and a new order-statistics sampler.","core_discovery":"The paper's central discovery is Theorem 3.1: for Balls-and-Bins sampling, the adaptive-batch linear-query mechanism $\\mathrm{ABLQ}_B$ is tightly characterized by the pair $P_B = \\frac{1}{T}\\sum_{t=1}^T \\mathcal{N}(e_t, \\sigma^2 I_T)$ and $Q_B = \\mathcal{N}(0, \\sigma^2 I_T)$, so $\\delta_B(\\varepsilon) = \\max\\{D_{e^\\varepsilon}(P_B \\| Q_B), D_{e^\\varepsilon}(Q_B \\| P_B)\\}$. This tight pair lets the paper prove that Balls-and-Bins is never less private than shuffling or deterministic batching, and that in the large-$\\varepsilon$ regime it is strictly more private than Poisson subsampling, which prior work had shown can be worse than even deterministic batching. It also provides the basis for a practical Monte Carlo accountant that combines importance sampling with order-statistics sampling to estimate these divergences for up to a million steps, and experiments on two large ad-prediction datasets show that DP-SGD with Balls-and-Bins matches shuffled DP-SGD's utility at the same noise multiplier.","pith_inferences":["Editorial inference: because the paper shows $(P_B,Q_B)$ and $(P_P,Q_P)$ are incomparable rather than one dominating the other, a defensible practical rule is to prefer Balls-and-Bins when the target $\\varepsilon$ is large and to re-check with Monte Carlo when $\\delta_P$ is very small; the paper itself stops short of stating such a selection rule.","Editorial inference: the order-statistics sampling estimator is presented as 'of independent interest beyond DP'; a concrete adjacent use is approximating sums of log-normal random variables via the Ben Slimane-type bounds the method generalizes, which the paper does not explore.","Editorial inference: multi-epoch training, the common real-world configuration, is only sketched in Appendix B.4; a natural next test is running the multi-epoch estimator (Algorithm 11) on the same Criteo setups to see whether $\\delta_B$ stays below $\\delta_P$ after several epochs, something the paper leaves untested."],"forward_implications":["For every $\\varepsilon>0$, $\\delta_B(\\varepsilon) \\le \\delta_S(\\varepsilon) \\le \\delta_D(\\varepsilon)$; Balls-and-Bins is never less private than shuffling or deterministic batching at the same noise scale and step count.","For sufficiently large $\\varepsilon$, $\\delta_B(\\varepsilon) < \\delta_P(\\varepsilon)$; in the high-$\\varepsilon$ regime Balls-and-Bins is strictly more private than Poisson subsampling, reversing the gap that prior work found for shuffling.","Because each batch has the same marginal distribution as a Poisson batch, the per-step gradient estimates look Poisson-like, yet the sampler is implemented with a one-line change to a shuffle-based DP-SGD loop.","The Monte Carlo accountant with importance sampling and order-statistics sampling estimates $\\delta_B(\\varepsilon)$ for up to $T=10^6$ steps in minutes on commodity hardware, making privacy accounting feasible at production scale.","On the two large Criteo datasets used in the experiments, DP-SGD with Balls-and-Bins matches shuffled DP-SGD in AUC at the same noise multiplier, while the sampled privacy bounds lie below those of Poisson in the regimes shown."],"supporting_citations":[{"why":"Formalizes the ABLQ mechanism, exhibits the pair $(P_S,Q_S)$ dominated by shuffling, and proves shuffling can be less private than Poisson; the paper aims to beat this.","marker":"Chua et al. (2024a)"},{"why":"Provides the tightly dominating pair for the deterministic batch generator, giving the baseline $\\delta_D$ used in the ordering.","marker":"Balle and Wang (2018)"},{"why":"Provide the tightly dominating pair for Poisson subsampling, giving $\\delta_P$ as the comparison target for the privacy ordering.","marker":"Koskela et al. (2020); Zhu et al. (2022)"},{"why":"Supplies the scalable batch-sampling implementation and the batch-cap truncation accounting used in the experiments.","marker":"Chua et al. (2024b)"},{"why":"Introduces the randomized Monte Carlo privacy accounting approach that Algorithm 4 builds on for upper-bounding the hockey-stick divergence.","marker":"Wang et al. (2023)"},{"why":"Gives the log-normal sum bounds that the order-statistics approximations generalize for efficient sampling when $T$ is large.","marker":"Ben Slimane (2001)"},{"why":"Subsequent result, cited in the Discussion, supporting the claim that Balls-and-Bins is asymptotically no worse than Poisson subsampling.","marker":"Feldman and Shenfeld (2025)"}],"fun_headline_variants":["Balls-and-Bins DP-SGD: shuffle-grade utility, Poisson-grade privacy","New sampler for DP-SGD matches shuffle utility and Poisson privacy","Balls-and-Bins sampling gives DP-SGD tight privacy and real utility","DP-SGD gets a sampler that's both shuffle-like and Poisson-private","Tight privacy for DP-SGD from Balls-and-Bins sampling"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The practical claim that Balls-and-Bins is at least as private as Poisson in realistic regimes rests on Monte Carlo upper bounds that the paper's own Figure 2 shows become inconclusive once the target $\\delta$ falls below roughly $10^{-7}$, and the paper concedes that a tight provable accounting for $\\mathrm{ABLQ}_B$ remains open.","fun_headline_variants_meta":{"raw":{"variants":["Balls-and-Bins DP-SGD: shuffle-grade utility, Poisson-grade privacy","New sampler for DP-SGD matches shuffle utility and Poisson privacy","Balls-and-Bins sampling gives DP-SGD tight privacy and real utility","DP-SGD gets a sampler that's both shuffle-like and Poisson-private","Tight privacy for DP-SGD from Balls-and-Bins sampling"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00022,"raw_usage":{"total_tokens":1457,"prompt_tokens":963,"completion_tokens":494,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":579,"completion_tokens_details":{"reasoning_tokens":397}},"tokens_in":579,"tokens_out":494,"duration_ms":4234,"temperature":1.0,"reasoning_tokens":397,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T10:16:22.072248+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute $\\delta_B(\\varepsilon)$ with a provably tight accountant---for instance the characteristic-function or privacy-loss-distribution method already used for Poisson---at the Figure 2 configurations where the Monte Carlo bounds were inconclusive, such as $T=4517$, $\\sigma=0.3$, $\\varepsilon$ near $10$ with $\\delta_P \\approx 10^{-8}$; if the exact $\\delta_B$ exceeds $\\delta_P$ there, the best-of-both claim fails in a practical regime.","supporting_citations":[{"cited_title":"Improving the gaussian mechanism for differential privacy: Analytical calibration and optimal denoising","cited_arxiv_id":null,"evidence_quote":"Provides the tightly dominating pair for the deterministic batch generator, giving the baseline $\\delta_D$ used in the ordering."},{"cited_title":"A randomized approach to tight privacy accounting","cited_arxiv_id":null,"evidence_quote":"Introduces the randomized Monte Carlo privacy accounting approach that Algorithm 4 builds on for upper-bounding the hockey-stick divergence."}],"review_version":1}