Pith. sign in

REVIEW 2 major objections 3 minor 5 references

Efficient privacy loss accounting for subsampling and random allocation

T0 review · 2 major / 3 minor · reviewed 2026-08-02 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2602.17284 v2 pith:KDXIWPXU submitted 2026-02-19 cs.LG

Vitaly Feldman , Moshe Shenfeld This is my paper · ORCID
classification cs.LG
keywords differentialprivacylossdistributionrandomallocationPoissonsubsamplingamplificationDP-SGDGaussianmechanismnumericalaccounting
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 3 minor

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.

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 (2)
  1. [Abstract, Section 1.1, Section 6, Figure 7] 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.
  2. [Section 1.1, Lemma 2.7] 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
minor comments (3)
  1. [Appendix B, proof of Theorem 4.6] 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.
  2. [Algorithm 6 (Appendix C)] 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.
  3. [Section 5] 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.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the PLD transformation is derived from the definition of privacy loss; cited dominating-pair reductions are external inputs, and the only caveat is a tightness statement inherited from the authors' prior work.

full rationale

The derivation chain is self-contained at its core. Theorem 4.4 obtains the random-allocation PLD as an explicit function of the input PLD by algebraic manipulation of the density ratio, and Theorem 3.3 derives the Poisson-subsampling transformation from the same definition. Theorem 4.6's validity and tightness proofs use only stochastic domination, discretization, and convolution lemmas proved in the appendix; no parameter is fitted to a target quantity and then renamed a prediction. The algorithm takes a PLD realization of a dominating pair as input and returns a bound; the runtime's IQR dependence is an accuracy-driven discretization, not a data fit. The reduction from an adaptive algorithm M to a fixed randomizer R (Lemma 2.7, from Feldman & Shenfeld 2025) and the k-to-1 reduction (Lemma 2.8) are prior theorems used as inputs; they are parameter-free, their assumptions do not include the PLD result being computed, and they are therefore legitimate external evidence under the stated citation rule. The one load-bearing caveat appears in Section 1.1: 'As discussed in prior work, this reduction is tight for many private algorithms that include DP-SGD with sufficiently rich loss functions...' This tightness is asserted by citation to prior work (including the authors' own) rather than proved here. That is a verification/completeness gap for the practical DP-SGD claim, but not circularity: the algorithm's upper bound remains valid even if the reduction is loose. No self-definitional equation, fitted-input-as-prediction, or ansatz-via-self-citation chain appears.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No physical or empirical entities are introduced; 'PLD realization' is a formal mathematical definition rather than a postulated entity. There are no fitted free parameters: alpha and beta are user-chosen accuracy targets, and sigma/t/delta are inputs from the application.

assumptions (4)
  • domain assumption Dominating-randomizer reduction: an adaptive t-step algorithm M is dominated by a fixed randomizer R, so random allocation of M is dominated by random allocation of R (Lemma 2.7).
    The paper relies on this for its 'any DP algorithm' framing; it is cited from Feldman & Shenfeld 2025 and acknowledged to be tight only for many natural algorithms such as DP-SGD with rich loss functions. General algorithms with path-dependent privacy loss may not be tightly captured.
  • domain assumption k-out-of-t random allocation reduces to k-fold composition of 1-out-of-floor(t/k) allocation (Lemma 2.8).
    Used to extend the algorithm to general k. The reduction is lossy when floor(t/k) is small, and the paper acknowledges this can make the bound suboptimal.
  • standard math The Gaussian mechanism with sensitivity 1 has dominating pair N(1, sigma^2) and N(0, sigma^2).
    Standard result (Zhu et al. 2022), used for all numerical evaluations and for the concrete runtime bound O(log^3 t log(t/beta)/(sigma^2 alpha^2)).
  • domain assumption Discretization and rounding performed in the numerical algorithm preserve stochastic domination and PLD-realization properties in exact real arithmetic.
    The proofs of Theorem 4.6 assume exact arithmetic; the actual floating-point implementation may introduce additional errors at very small delta, which the paper mitigates with float128 and other measures.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Efficient privacy loss accounting for subsampling and random allocation." pith.science (2026). https://pith.science/paper/KDXIWPXU

@misc{pith2026260217284,
  author       = {Pith},
  title        = {Pith review of: Efficient privacy loss accounting for subsampling and random allocation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KDXIWPXU}},
  note         = {Machine review of arXiv:2602.17284}
}
abstract

We consider the privacy amplification properties of a sampling scheme in which a user's data isused in $k$ steps chosen randomly and uniformly from a sequence (or set) of $t$ steps. This sampling scheme has been recently applied in the context of differentially private optimization (Chua et al., 2024a; Choquette-Choo et al., 2025) and communication-efficient high-dimensional private aggregation (Asi et al., 2026), where it was shown to have utility advantages over the standard Poisson sampling. Theoretical analyses of this sampling scheme (Feldman & Shenfeld, 2025; Dong et al., 2025) lead to bounds that are close to those of Poisson sampling, yet still have two significant shortcomings. First, in many practical settings, the resulting privacy parameters are not tight due to the approximation steps in the analysis. Second, the computed parameters are either the hockey stick or Renyi divergence, both of which introduce overheads when used in privacy loss accounting. In this work, we demonstrate that the privacy loss distribution (PLD) of random allocation applied to any differentially private algorithm can be computed efficiently. When applied to the Gaussian mechanism, our results demonstrate that the privacy-utility trade-off for random allocation is at least as good as that of Poisson subsampling. In particular, random allocation is better suited for training via DP-SGD. To support these computations, our work develops new tools for general privacy loss accounting based on a notion of PLD realization. This notion allows us to extend accurate privacy loss accounting to subsampling which previously required manual noise-mechanism-specific analysis.

Figures

Figures reproduced from arXiv: 2602.17284 by the authors.

Figure 1
Figure 1. Upper and lower bounds on privacy parameter [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Comparison of the privacy profile of the Poisson scheme and various bounds for the random [PITH_FULL_IMAGE:figures/full_fig_p013_2.png] view at source ↗
Figure 3
Figure 3. Runtime as a function of accuracy α and number of steps t on Apple MacBook Pro M1, using σ = 1. Privacy-utility trade-off: Chua et al. (2024a) demonstrated the utility advantage of the random allocation scheme relative to Poisson subsampling. In their experiments they train neural networks on a dataset of size n using DP-SGD with a fixed noise level σ and expected batch size B, and show that sampling using random al… view at source ↗
Figures from the paper (8 more)
Figure 4
Figure 4. Figure 4: Analytical and empirical square error for the Poisson and random allocation scheme using both [PITH_FULL_IMAGE:figures/full_fig_p014_4.png]
Figure 5
Figure 5. Figure 5: The ratio between the noise level required to achieve ( [PITH_FULL_IMAGE:figures/full_fig_p015_5.png]
Figure 6
Figure 6. Figure 6: Comparison of the privacy profile of the Poisson scheme and various bounds for the random [PITH_FULL_IMAGE:figures/full_fig_p028_6.png]
Figure 7
Figure 7. Figure 7: Privacy profile of the Poisson and random allocation schemes for [PITH_FULL_IMAGE:figures/full_fig_p029_7.png]
Figure 8
Figure 8. Figure 8: portrays this phenomenon. Since the FFT-based convolution typically requires more memory while the direct multiplicative-based method results in longer runtime, there is no natural comparison between the two. We chose to use the number of bins as the comparison value, …
Figure 9
Figure 9. Figure 9: Comparison of numerical and analytic bounds on the 2nd order RDP of the random allocation [PITH_FULL_IMAGE:figures/full_fig_p030_9.png]
Figure 10
Figure 10. Figure 10: Upper and lower bounds on privacy parameter [PITH_FULL_IMAGE:figures/full_fig_p030_10.png]
Figure 11
Figure 11. Figure 11: Upper and lower bounds on privacy parameter [PITH_FULL_IMAGE:figures/full_fig_p031_11.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

5 extracted references

  1. [1]

    There exists two PLD realizations V, U such that U stochastically dominates V but D(U) does not stochastically dominatesD(V)nor dominated by it

  2. [2]

    There exists λ∈ [0, 1]and two random variables V, Usuch that U stochastically dominates V but ⃗ φλ(U ) does not stochastically dominates⃗ φλ(V)nor dominated by it

  3. [3]

    20 Proof

    For any two PLD realizationsV, U, ifV⪯UthenD(U)⪯ (0,c) D(V)wherec :=f U (∞)−f V (∞). 20 Proof. First part:Consider the random variables V, Uover {ln(2),ln (4)}, such that fV (ln(2)) = fU (ln(4)) = 0.6 and fV (ln(4)) = fU (ln(2)) = 0.4. Clearly, both are PLD realizations, and U stochastically dominates V . Their duals are fD(V) (−ln (4)) = 0 .1, fD(V) (−ln...

    2007

  4. [4]

    Since the number of iterations in Algorithm 3 is bounded by ⌈log2(t)⌉, and each iteration contains at most 2 convolutions, the number of times Algorithm 4 is called with inputtis at most 2⌈log 2(t)⌉. 22

  5. [5]

    P ¯l[j]+¯l′[k]∈[¯lconv[i],¯lconv[i+1]) fX [j]·f X ′[k] # i∈[n] {Denoting ¯lconv[n+ 1] =∞} fconv(−∞)←0,f conv(∞)←1− P i∈[n] fconv[i] else fconv ←

    If both input distributions to Algorithm 4 are defined over the grids a·e α·i i∈[n+1], b·e α·i i∈[n+1], then the output distribution is defined over the grid (a+b)·e α·i i∈[n+1]. This is because by definition, the output grid is supported over the range (( a + b) ·e α, (a + b) ·e (n+1)α), and it is spaced with constant ratioα, so its size is log α (a+b)·e...

    2025

Pith tools

Reviewed August 2, 2026 · model on record in the stance chip above.