{"id":"6bc16de0-d59f-406f-8de2-aca684333a42","arxiv_id":"2602.17284","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A new PLD-based accounting method computes tight privacy-loss distributions for random allocation, showing it can match or beat Poisson subsampling in practical DP-SGD settings.","lead":"This paper shows how to efficiently and tightly compute the privacy-loss distribution of k-out-of-t random allocation from any base differentially private mechanism. It gives practical privacy accounting that lets DP-SGD-style training with random sampling use less noise than Poisson-subsampling baselines.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"DP-SGD tightness depends on Lemma 2.7's reduction to a fixed randomizer, which is asserted only for 'sufficiently rich' losses; if loose, the computed PLD is a valid but overly pessimistic bound.","rationale":"The reader identified the tightness of Lemma 2.7 as the weakest assumption, and I agree. The algorithmic core—Theorem 4.4 and Theorem 4.6—is proved in detail: the PLD of the dominating pair is computed via exp-PLD convolution, tightness is argued via (α,β)-stochastic domination, and the runtime bound is derived. This is solid. The caveat is that this computes the PLD of the *dominating randomizer* (Claim 2.9), not of the actual adaptive algorithm M. The transfer from M to its dominating randomizer (Lemma 2.7) is valid as an upper bound, but its tightness for DP-SGD is only asserted via prior work for 'sufficiently rich loss functions.' If that reduction is loose for realistic DP-SGD, the computed bounds are conservative and the paper's claim that random allocation is 'at least as good as Poisson' is not established. The paper's own Figure 7 shows the two sampling schemes are incomparable in extreme regimes, so the abstract's 'at least as good' is at best a domain-restricted claim. The proposed Monte Carlo test directly checks whether the bound matches the algorithm's true privacy loss in a representative DP-SGD setting, which would settle the concern. Overall, the reader's CONDITIONAL verdict remains appropriate.","tokens_in":26513,"tokens_out":13238,"duration_ms":111256,"concrete_test":"Empirically test tightness of Lemma 2.7 for DP-SGD: implement DP-SGD with 1-out-of-t random allocation (small model, e.g., logistic regression on synthetic data), fix a user, and estimate their privacy loss distribution by Monte Carlo over the algorithm's randomness (allocation + Gaussian noise). Compare the empirical tail (e.g., δ at several ε) to the PLD bound produced by the paper's code (Shenfeld, 2026) using the same σ,t. If the empirical tail is substantially below the bound (ε gap > α at fixed δ), the reduction is loose in practice and the 'tight accounting for DP-SGD' claim is unsupported; if they match, the concern is resolved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central practical claim—that random allocation is a tightly-accountable alternative to Poisson in DP-SGD—requires two tightness steps: (i) the (α,β)-tight approximation of the PLD of the dominating pair (Theorem 4.6), and (ii) the tightness of the reduction from the adaptive t-step algorithm M to a fixed randomizer R (Lemma 2.7, from Feldman & Shenfeld 2025). Step (i) is proved in the paper. Step (ii) is not. The paper states (Section 1.1, after Lemma 2.7) that the reduction is 'tight for many natural choices of M' and cites prior work for DP-SGD 'with sufficiently rich loss functions,' but offers no formal condition or proof. If M's per-step privacy loss depends on the view in a way not captured by the fixed worst-case pair (P,Q), then the dominating pair for At(R) is a relaxation of At(M), and the computed PLD—while a valid upper bound—may be substantially looser than the true privacy loss of DP-SGD. The abstract's 'any differentially private algorithm' phrasing and the 'at least as good as Poisson' comparison inherit this unverified tightness. The paper's own Figure 7 already demonstrates that random allocation and Poisson are incomparable in some regimes, so the comparative claim is scoped too broadly even under tightness.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops an efficient numerical method for computing the privacy loss distribution (PLD) of the k-out-of-t random-allocation sampling scheme. The central technical contribution is a transformation (Theorem 4.4) expressing the PLD of the dominating pair for random allocation as a convolution of exponentiated PLDs, together with a discretization and direct-convolution algorithm that produces (α, β)-tightly stochastically dominating PLD realizations in O((IQR_{β/t}/α)^2 log^3 t) time (Theorem 4.6). The authors also introduce 'PLD realizations' as a representation that supports subsampling (Theorem 3.3) and can be composed with standard PLD accounting. Numerical experiments compare the resulting bounds with prior analytic bounds, Monte Carlo estimates, and Poisson subsampling, and include a DP-SGD/PREAMBLE case study. The abstract and Section 6 claim that random allocation is 'at least as good' as Poisson subsampling and is 'better and more practical' for DP-SGD.","tokens_in":26819,"tokens_out":16047,"duration_ms":134605,"significance":"If the main claims are taken at face value, this is a substantial advance in privacy accounting: it provides the first practical, tight-looking numerical PLD computation for random allocation, a scheme used in recent DP-SGD and private aggregation work. The PLD-realization framework is a useful conceptual tool, and the paper ships an open-source implementation (Shenfeld, 2026). The formal results in Section 4 — in particular Theorem 4.4 and the stochastic-domination preservation of Lemma 4.5 — are the core contribution and appear technically sound. The significance is somewhat reduced by two framing gaps: the abstract's universal 'any differentially private algorithm' and the 'at least as good as Poisson' comparison are not supported by the paper's own incomparability result (Figure 7, Appendix D), and the practical tightness for DP-SGD depends on an unproven tightness assumption in Lemma 2.7.","major_comments":[{"comment":"The abstract and Section 6 claim that random allocation has a privacy-utility trade-off 'at least as good' as Poisson subsampling and is a 'better and more practical alternative'. This is contradicted by the paper's own Figure 7 and Appendix D, which state that the Poisson scheme is neither dominated by random allocation nor dominates it. Figure 7 shows crossing privacy profiles for σ=1, t=2, and the text in Appendix D explicitly says the two schemes are incomparable. Section 1.1 also says our results are 'never worse than the bounds for Poisson subsampling', which is not true in the ε≪1 regime shown in Figure 7. The claims should be scoped to the practical parameter regimes demonstrated (e.g., 'for the settings considered in this paper') and the incomparability caveat should be stated clearly in the abstract and introduction.","section":"Abstract, Section 1.1, Section 6, Figure 7"},{"comment":"The central practical claim — that random allocation is tightly accountable for DP-SGD — relies on Lemma 2.7 (from Feldman & Shenfeld 2025), which reduces an arbitrary adaptive t-step algorithm M to a fixed dominating randomizer R. This reduction is a domination, not a tightness statement. The manuscript acknowledges (after Lemma 2.7) that tightness holds only 'for many natural choices' and for DP-SGD with 'sufficiently rich loss functions', but gives no formal condition or proof. The abstract's 'any differentially private algorithm' and the claim that the PLD of random allocation 'can be computed efficiently' therefore overstate the result: the algorithm computes a valid upper bound on the PLD of the dominating pair, but if the reduction is loose, the bound may be substantially pessimistic for the actual algorithm. The numerical lower bounds in Figures 1 and 10 are for the dominating pa","section":"Section 1.1, Lemma 2.7"}],"minor_comments":[{"comment":"The complexity proof states the total running time is O(n0^2 · log^2(t)), but the preceding counting gives O(n0^2 · log t) convolution calls, and n0 = (IQR/α)(2⌈log t⌉+1) already contributes log^2 t. The final theorem's O((IQR/α)^2 log^3 t) is consistent with O(n0^2 · log t), so the proof's 'log^2' appears to be a typo.","section":"Appendix B, proof of Theorem 4.6"},{"comment":"The pseudo-code for disc-dist in the 'lower' branch is ambiguous: the definition of the F_U array and the index convention in 'fU ← [F_U[i]−F_U[i−1]]' are not sufficiently precise to determine whether the rounding is to the left or right. A worked example or a clearer statement of the array indices would help reproducibility.","section":"Algorithm 6 (Appendix C)"},{"comment":"The sentence 'Our results are nearly indistinguishable from the lower bound' should clarify that this lower bound is for the dominating pair (the random-allocation scheme), not for the original DP-SGD algorithm. This is related to the tightness caveat in the second major comment.","section":"Section 5"}],"recommendation":"major_revision","confidential_remarks":"The technical core — Theorem 4.4 and the stochastic-domination-preserving discretization algorithm — is sound and is the main contribution. The paper's impact is currently undermined by overclaiming in the abstract and Section 6, and by an unresolved tightness assumption inherited from Lemma 2.7. If the authors scoped the claims to 'upper bounds on the dominating pair' and explicitly flagged the DP-SGD tightness caveat, the paper would be a strong fit for the journal. The reader's conditional verdict is well aligned with my assessment."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The thing to know: the core algorithm is sound and practically useful, and the paper overreaches only in the comparative marketing. The new machinery is the PLD-realization formalism and the exp-PLD convolution for 1-out-of-t random allocation, with (α,β)-tight stochastic domination guarantees and O(log^3 t · (IQR/α)^2) runtime. They prove the transformation in Theorem 4.4, give discretization and tightness in Theorem 4.6, ship code, and show bounds that sit almost on top of Monte Carlo lower bounds while beating prior analytic RDP/hockey-stick analyses. That closes a real gap: PLD-based accounting for random allocation, which existing libraries couldn't do.\n\nDo I buy it? Mostly. The derivations in Section 4 and the appendices check out at a reading level; the discretization error argument via Lemma 4.5 is clever and seems right. The implementation is not formally verified, but the pseudo-code is complete and the empirical lower/upper bounds nearly overlap, which is good evidence. The main caveat is one the paper itself flags: the whole pipeline inherits Lemma 2.7, a reduction from an arbitrary adaptive t-step algorithm to a fixed randomizer, cited from Feldman & Shenfeld 2025. Tightness of that reduction is asserted for 'sufficiently rich' losses, not proven here. So the computed PLD is a valid upper bound always, but it might be loose for mechanisms where the per-step privacy loss depends on the view in ways the fixed pair (P,Q) doesn't capture. That's worth stating as a limitation, not a fatal flaw.\n\nThe other soft spot is the 'at least as good as Poisson' sentence in the abstract and Section 6. It's contradicted by their own Figure 7 (and Appendix D note) showing the two schemes are incomparable in general. The accurate claim is 'better in the parameter regimes we tested for DP-SGD-style settings.' That's a scoping fix, not a rework.\n\nWho's it for: anyone doing DP-SGD privacy accounting, especially PLD users. It deserves a serious referee; the math is intricate and the comparative claims need a careful pass. I'd send it to review.","headline":"The PLD accounting for random allocation is a real contribution; just trim the 'at least as good as Poisson' claim, which their own Figure 7 contradicts.","tokens_in":27301,"tokens_out":1905,"would_cite":true,"duration_ms":16862,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"An efficient, tight algorithm now computes the privacy loss distribution of random-allocation sampling, and shows the scheme matches or beats Poisson subsampling in DP-SGD's privacy–utility trade-off.","keywords":["differential privacy","privacy loss distribution","random allocation","Poisson subsampling","privacy amplification","DP-SGD","Gaussian mechanism","numerical privacy accounting"],"falsifier":"Compute the exact PLD of 1-out-of-t random allocation for the Gaussian mechanism at small t (say t = 2 or 3) by brute-force numerical quadrature; if the algorithm's output is not within its claimed (α, β) tightness of the true PLD, Theorem 4.6 falls. Separately, for the practical claim: run a membership-inference audit on DP-SGD trained with random allocation under the paper's accounted parameters; measured remove-direction privacy loss exceeding the computed bound at the claimed δ would show the fixed-randomizer reduction is not tight for real adaptive training.","tokens_in":26385,"feed_emoji":"🔐","tokens_out":16991,"duration_ms":134344,"temperature":0.7,"pith_summary":"Random allocation — each data element is used in exactly k of t steps rather than being independently re-included at every step — is a sampling scheme with demonstrated utility advantages over Poisson sampling in DP-SGD and in communication-efficient private aggregation, but its privacy cost could previously only be bounded loosely, via Monte Carlo simulation without formal guarantees, or via Rényi-divergence and hockey-stick-divergence bounds that lose tightness when composed. The paper claims this gap is closed: the privacy loss distribution (PLD) of 1-out-of-t random allocation is shown to be a log of a sum of exponentiated per-step privacy losses, reducing the computation to convolutions that run in time polylogarithmic in t and inverse-quadratic in the desired accuracy. For the Gaussian mechanism the resulting bounds are nearly tight, never worse than Poisson in practical regimes, and cheap enough for routine use; together with prior utility results this implies random allocation has a privacy–utility trade-off at least as good as Poisson subsampling, so DP-SGD can be trained with exactly-k-per-example batches and reported with rigorous (ε, δ) guarantees. A new notion — the PLD realization — makes subsampling itself a lossless operation on privacy-loss representations, enabling end-to-end accounting of nested schemes. The reason a general reader should care is that this removes the mismatch between how DP-SGD is implemented in practice and how its privacy is certified.","feed_headline":"Random-allocation privacy bounds now tight in seconds","feed_subtitle":"It matches or beats Poisson on privacy–utility in DP-SGD, so the practical scheme now has rigorous accounting.","key_machinery":"PLD realization: a discrete random variable L with E[e^{−L}] ≤ 1 and f_L(−∞) = 0 that encodes a dominating pair (P, Q) while remaining composable. The carrying identity (Theorem 4.4): random-allocation privacy loss is the log of a normalized sum of exponentiated privacy losses, with the dual D(L), f_{D(L)}(l) = f_L(−l)e^l, supplying the add direction — so sampling becomes t-fold convolution of one-dimensional exp-PLDs. Convolution runs on a multiplicative (constant-ratio) grid instead of FFT's additive grid, since exponentials of Gaussian losses are log-normal with extreme dynamic range; a domination-preserving discretization rounds probability mass conservatively after every squaring step.","core_discovery":"The central discovery is an identity (Theorem 4.4): the privacy loss of 1-out-of-t random allocation equals the log of a normalized sum of exponentiated per-step privacy losses, with the add direction negated. Because any t-step algorithm is dominated by a fixed randomizer, this reduces an intractable high-dimensional mixture to t-fold convolutions of one-dimensional losses, computed on a multiplicative grid by exponentiation by squaring in O((IQR_{β/t}/α)^2 log^3 t) time (Theorem 4.6), with (α, β)-tight stochastic domination. For Gaussian noise the bounds are nearly indistinguishable from numerical lower bounds, never worse than Poisson subsampling in practical settings, and take seconds.","pith_inferences":["If the dominating-pair reduction turns out to be tight for real DP-SGD runs, the long-standing discrepancy between implementations that shuffle batches and analyses that assume Poisson sampling can be retired: the exact-participation scheme being certified is the one actually executed.","The log-sum-exp identity and its multiplicative-grid convolution are likely to transfer to other mixture-of-distributions computations — fixed-size sampling without replacement, sharded selection, shuffle-model accountants — wherever a private output is a uniform mixture of per-step laws.","A direct empirical check of the practical claim: run DP-SGD with random allocation and audit it with a membership-inference adversary; if the measured remove-direction privacy loss ever exceeds the computed PLD bound at the claimed δ, the fixed-randomizer reduction would be falsified for that mechanism.","The paper's bounds cover the privacy side of the trade-off; the utility side comes from prior experiments. The combined claim — strictly better privacy–utility than Poisson — would be strengthened by a full end-to-end training study reporting both curves at matched noise and compute."],"forward_implications":["DP-SGD can be trained with exactly-k-participations-per-example batches — the scheme with better utility — and reported with (ε, δ) guarantees as tight as, and often tighter than, Poisson sampling's.","Subsampling accounting no longer needs a per-mechanism analytic derivation: any noise distribution can be accounted via PLD realizations, unlike current libraries restricted to Gaussian and Laplace mechanisms.","Nested and composed schemes (random allocation inside Poisson-sampled epochs, communication-limited aggregation in federated learning) can be accounted end-to-end in the PLD format, avoiding the 10–20% overhead of Rényi-to-(ε, δ) conversion.","The O((IQR_{β/t}/α)^2 log^3 t) runtime makes the accountant practical — seconds on a laptop in realistic regimes — where prior high-confidence Monte Carlo estimates were computationally infeasible."],"fun_headline_variants":["Random-allocation privacy accounting now tight and in seconds","Tight privacy loss for random allocation computed in seconds","Random allocation privacy bounds now match or beat Poisson in DP-SGD","Random allocation privacy accounting: tight and fast"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The load-bearing premise is that an arbitrary adaptive t-step algorithm — DP-SGD included — has its worst-case privacy loss exactly captured by a fixed randomizer with one 'data present' distribution and one 'data absent' distribution. If a real mechanism's per-step privacy loss depends on the accumulated history of outputs in a way no such fixed pair captures, the computed PLD bounds a simplified version of the algorithm rather than the algorithm itself.","fun_headline_variants_meta":{"raw":{"variants":["Random-allocation privacy accounting now tight and in seconds","Tight privacy loss for random allocation computed in seconds","Random allocation privacy bounds now match or beat Poisson in DP-SGD","Random allocation privacy accounting: tight and fast"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000674,"raw_usage":{"total_tokens":2949,"prompt_tokens":831,"completion_tokens":2118,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":575,"completion_tokens_details":{"reasoning_tokens":2054}},"tokens_in":575,"tokens_out":2118,"duration_ms":13699,"temperature":1.0,"reasoning_tokens":2054,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-02T22:16:10.526328+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the exact PLD of 1-out-of-t random allocation for the Gaussian mechanism at small t (say t = 2 or 3) by brute-force numerical quadrature; if the algorithm's output is not within its claimed (α, β) tightness of the true PLD, Theorem 4.6 falls. Separately, for the practical claim: run a membership-inference audit on DP-SGD trained with random allocation under the paper's accounted parameters; measured remove-direction privacy loss exceeding the computed bound at the claimed δ would show the fixed-randomizer reduction is not tight for real adaptive training.","supporting_citations":[],"review_version":1}