Counting on Dummies: Privacy Amplification with Observable Counts and Truncated Batches

Introduction

Differentially private stochastic gradient descent (DP-SGD) is the standard algorithm for training machine-learning models under differential privacy [1, 8]. Its privacy analysis rests on privacy amplification by subsampling: because each step operates on a small randomly chosen batch, the relatively weak privacy guarantee of a single noisy gradient step is amplified significantly. This enables the release of the numerous noisy gradients with reasonable privacy guarantees for the entire run. The strongest and most widely used amplification comes from schemes in which each batch is a genuinely random subset of the data: Poisson subsampling, which includes each example independently with probability $\gamma$ [1, 44], and, more recently, random allocation, a balls-in-bins scheme that spreads each example across a random subset of the steps [23]. Both schemes admit tight and efficient accounting, based on dominating pairs of distributions [44] and implemented via numerical computations on privacy loss distributions (PLDs).

An important feature of these schemes is that they produce batches of variable size, distributed as a binomial random variable. The size of a batch is thus a random quantity that depends on the internal randomization of the algorithm. The amplification guarantees of these schemes implicitly assume that the batch size is never revealed, that is, that the adversary observes only the per-step outputs. Under a trusted central curator this assumption is typically harmless. However, in federated and distributed deployments, where contributions from many devices are aggregated without a trusted central party, the server that performs the aggregation typically does observe each batch’s size, for example, by counting the number of messages it combines. Once the size is observed, the amplification analysis no longer applies as stated, and the resulting leakage erodes the privacy guarantees. Related gaps between the idealized sampling assumed in analyses and the batching actually realized in implementations are by now a recognized source of privacy violations [14, 2, 33]. Indeed, in federated settings the difficulty of realizing and hiding subsampling has led to the use of optimization methods that abandon sampling altogether [32].

Variable batch sizes present another, independent difficulty. Memory and compute budgets typically impose an a priori cap $s$ on the batch size, so any batch exceeding $s$ must be truncated to fit. In common training pipeline designs, the batch also needs to be padded to have the fixed size $s$. Similarly in distributed aggregation implementations, system constraints can force a maximum batch size. Truncation, however, breaks the privacy accounting under the add/remove and zero-out adjacency notions that are typically used in this context. When the batch size is fixed (or otherwise known), removing a data point from a full batch means that another data point takes its place, so the batch sum can shift by two gradients rather than one. This effectively doubles the sensitivity and thus requires doubling the noise scale. Recent work of Ganesh [27] gives a tighter, dedicated analysis of truncated Poisson sampling, but the doubled sensitivity remains: it is charged whenever the batch overflows, which forces the expected batch size to be well below $s$. We provide a more detailed discussion in § 1.3.

Our results

We resolve both these difficulties with a single, simple technique that we call dummy count masking. Throughout, the count of a batch is the number of contributions it holds: without truncation this is exactly the batch size, and with truncation it is the pre-truncation size. Before releasing the count, we add a random number of dummy points to the batch. A dummy is a fixed reference element $\bot$, which in aggregation is simply the zero vector; for this reason, replacing a real point by $\bot$ is referred to as zero-out adjacency, and the privacy of such a replacement is controlled by the core mechanism. Crucially, the number of dummy points added is drawn from a fixed, public, data-independent distribution $\mathcal{C}$ over $\mathbb{Z}_{+}$. We then release the resulting (dummy-masked) count. In addition, if a truncation cap is imposed, we truncate the resulting batch to the fixed size $s$. If a fixed size $s$ is required we also pad the batches with fewer than $s$ elements using the same dummy element.

This has two effects. First, privatizing the count reduces to releasing a sensitivity-one integer statistic with one-sided noise, a problem studied in several contexts [12, 43]. Second, conditioned on the released count, a removed user is replaced by an additional dummy rather than by another user’s data, so the two neighboring batches differ in a single entry even after truncation and padding. Truncation thus preserves unit sensitivity instead of creating a sensitivity-two event.

Importantly, dummy count masking is compatible with distributed aggregation without a trusted curator. Each user decides independently, by local coin flips, whether to inject extra dummy messages into a batch and how many. With anonymous aggregation, dummy reports are indistinguishable from real ones, so the total number of dummies is hidden. Under distributed noise generation, each dummy message can carry its own noise share, so the scheme composes naturally with client-side noise generation and integrates easily into existing secure-aggregation pipelines.

We give a general privacy analysis of this mechanism for both Poisson subsampling and random allocation, showing that the additional privacy cost is typically dominated by the cost of the original algorithm. Our guarantees are stated as explicit dominating pairs of distributions, so that accurate numerical privacy accounting can be applied directly. We describe the simple steps needed to compute the privacy loss distribution of our mechanism and then demonstrate empirically that its privacy cost is typically negligible. We also compare the efficiency of our mechanism empirically with that of truncation without masking [27].

Overview of the analysis

We show (§ 4) that both the release of the masked count and the truncation can be folded into the per-step algorithm: the dummy-masked and (optionally) truncated scheme is exactly an ordinary sampling scheme applied to a modified batch algorithm. We then give a dominating pair of distributions for this batch algorithm in terms of a dominating pair for the original per-step mechanism, where a dominating pair of a mechanism is a pair of distributions whose hockey-stick divergence upper bounds the privacy loss of the mechanism. Specifically, if $(P_0, Q_0)$ is a remove-direction dominating pair of the per-step mechanism (the Gaussian noisy sum being the canonical example), we show that $(C_{+1} \times P_0, C \times Q_0)$ is a dominating pair of the modified batch algorithm, where $C$ is the distribution of the number of dummies and $C_{+1}$ is the distribution of $R+1$ for $R \sim C$. As a result, we never need to re-derive amplification theorems: it suffices to feed this dominating pair to the existing subsampling [44] and random-allocation [23] results.

Truncation is handled by isolating a stability property (§ 4.2). Conditioned on the released count, padding or truncating to size $s$ is a data-independent mixture of stable maps, that is, maps that transform batches differing in a single entry to batches differing in a single entry. By joint convexity of the hockey-stick divergence [6], pre-composing with such a map can only decrease every divergence, so it preserves dominating pairs (Lemma 4.4). The dominating pair for the batch algorithm above is therefore unchanged by truncation (Lemma 4.6).

Participant-generated dummies. In distributed applications of our mechanism the requirement that dummies are generated independently of batch participation may create a significant overhead in that each client may need to be actively communicating dummies across the entire execution of the algorithm. In particular, they may need to contribute dummies during rounds in which they are not contributing data. Thus we also analyze the version in which only the users that join a batch inject dummies into it (§ 6). In this case the count noise is coupled to participation. We show that our analysis framework can also handle this case (albeit with a different dominating pair of distributions). The analysis relies on an additional domination monotonicity argument for the batch size and a minimum-batch-participation event charged to $\delta$.

The cost of masking. The main computational overhead of our mechanism is the expected number of dummies per batch, $E_{R \sim C}[R]$. Released on its own, a count with one-sided (non-negative) noise requires noise of mean $\Theta(\frac{1}{\epsilon}\log\frac{1}{\delta})$ [12, 43]. Combining this with black-box amplification and composition theorems gives a per-batch mean of $O(\sigma^* \log(\gamma t/\delta))$ for $\sigma^* := \frac{\gamma\sqrt{2t\log(1/\delta)}}{\epsilon}$, where $\gamma$ is the Poisson subsampling rate and $t$ is the number of steps. In § 7 we show that the $\log(1/\delta)$ factor can be avoided in the CLT regime, where the privacy of the subsampled and composed count release is tightly controlled by the $\chi^2$ divergence of a single step [26]. We then show that, under the simplifying assumptions of the CLT regime, when masking the counts of a subsampled and composed or randomly allocated Gaussian mechanism with noise multiplier $\sigma$, a mean of $O(\frac{\sigma}{\sqrt{\alpha}}\log\frac{\sigma}{\sqrt{\alpha}})$ dummies suffices to ensure that the final $\epsilon$ grows by at most a factor of $1+\alpha$.

Why not simply privatize the counts? For one epoch of random allocation, the vector of batch counts is itself a sensitivity-one statistic, since deleting a user decrements a single count by one. One might therefore hope to privatize it on its own, by adding noise to each count, and simply pay for this release via standard composition theorems. The subtlety is that the two parts of the release share their randomness. The allocation that determines the counts is precisely the randomness whose secrecy drives privacy amplification for the noisy gradient sums, so once the (even noisy) counts are public, the amplification guarantee for the sums no longer applies as stated. More generally, it is well known that two correlated releases that are each differentially private may jointly reveal the input completely.¹

By folding the count release into the per-batch algorithm, we analyze the two components jointly, conditioning both on the shared sampling randomness. The joint analysis also gives better bounds: it effectively applies privacy amplification by subsampling to the count releases themselves, since a user’s presence affects any given count only with probability about $1/t$. By the asymptotics of § 7, the amplified count release needs noise of mean $\widetilde{O}\left(\frac{1}{\sqrt{t\varepsilon}}\right)$ per batch, smaller by a factor of $\widetilde{\Omega}(\sqrt{t})$ than the $\widetilde{\Theta}\left(\frac{1}{\varepsilon}\right)$ required by an unamplified sensitivity-one release with non-negative noise.

Why non-negative noise only? Since the primary goal of masking is to privatize the counts, it is natural to ask why we do not allow negative count noise: whenever the count noise $R$ is negative, one could drop $|R|$ randomly chosen elements from the batch. This is implementable when the server can manipulate batches arbitrarily before computing on them. It does not, however, fit our main motivation, the observability of message counts in a distributed setting with user-generated dummies, since a user cannot drop messages generated by other users. Moreover, our analysis conditions on the released count. With non-negative noise, the two conditional batches can be coupled as zero-out neighbors, so that the divergence of the outputs is controlled by the core mechanism. With deletions, conditioning on the count would change which real elements remain in the batch, and this coupling would no longer be possible.

Numerical Evaluation. By combining our results with numerical PLD accounting methods in [41, 25], we evaluate the privacy overheads of count masking empirically in two ways. We first consider two parameter settings corresponding to multi-epoch DP-SGD with both Poisson subsampling and random allocation. We consider several count noise distributions, including the simple binomial and negative binomial distributions (which can be generated in a distributed setting) with optimized parameters, and the count noise distribution optimized for minimizing the second moment under a fixed mean from [43]. In all settings, with the optimized negative binomial, the privacy overhead of masking is negligible ($<1\%$) once the expected number of dummies equals the standard deviation of the batch size. The overhead of the simple binomial is higher but still modest. We also evaluate the setting in which dummies are generated only by the participants of a batch: there, the overhead is essentially identical to that of independent dummies for larger batches and moderately higher for smaller ones (Figure 2).

We then consider the truncation setting where we have fixed maximum batch size. We compare the privacy cost of plain truncation via the analysis of Ganesh [27] with that of truncation after dummy masking, both under Poisson sampling. We show that empirically, adding dummies achieves a significantly lower privacy cost at the same batch efficiency (the expected fraction of real elements in the truncated batch). Importantly, count masking also makes truncation possible under random allocation, for which no alternative truncation analysis exists. Details of the experiments are provided in § 8.

Related work

Batch sampling in theory and practice. The gap between the sampling that DP-SGD analyses assume and the batching that implementations realize is by now well documented: batching by shuffling can result in substantially weaker privacy guarantees than the Poisson subsampling that is usually used for accounting [14, 15], and similar gaps arise for other deployed batching choices [2, 33]. Fixed-size pipelines have led practitioners to implement Poisson subsampling with truncation and padding [15], the route taken in recent large-scale differentially private language-model training [35 Vau25] and analyzed tightly by Ganesh [27]. Random allocation was proposed and analyzed as an alternative with more predictable participation [13, 11, 16, 23], with efficient PLD accounting given by Feldman and Shenfeld [24]. All of these analyses assume that the batch counts are hidden.

Truncated Poisson sampling. The closest prior work on privacy amplification with batch padding and truncation is that of Ganesh [27], who gives a tight privacy bound for truncated Poisson sampling of the subsampled Gaussian mechanism: each example is included independently with probability $p$, and a batch exceeding the cap $B$ is replaced by a uniformly random size-$B$ subset before the noisy gradient sum is released. Like ours, the analysis is phrased through dominating pairs, and it improves substantially on charging the overflow event to $\delta$, which would force the expected batch size well below $B$. Its central observation is that truncation doubles the sensitivity: when an added example displaces another from an already-full batch, the released sum can move by two gradients rather than one. The resulting dominating pair is a public mixture of an untruncated sensitivity-1 component and a truncated sensitivity-2 component, weighted by the (data-independent) overflow probability, so the doubling is paid only when truncation can occur. Our approach is orthogonal, and in principle the two can be combined; § 8 compares them empirically. Our analysis also applies beyond the Gaussian mechanism, to any per-step algorithm with a remove-direction dominating pair, and covers random allocation alongside Poisson subsampling.

Dummy messages in differential privacy. Injecting randomly generated dummy messages is a recurring idea in distributed and shuffle-model protocols. Balle et al. [4] and Ghazi et al. [28] realize private summation and counting in the shuffle model by having users send extra messages whose random contents implement the privacy noise, and study which noise distributions can be generated this way at the smallest message cost. Li et al. [34] amplify the privacy of shuffle-model protocols with dummy points, and in the augmented shuffle protocols of Murakami et al. [36] the shuffler itself injects, per item, a binomial (or asymmetric two-sided geometric) number of dummies so that the dummies alone realize the estimator’s noise. Dummies also defend against traffic analysis: Vuvuzela’s mix servers add random cover traffic so that the observable dead-drop access counts are differentially private [30], and in the private-search system Wally each client issues fake queries over an anonymous network so that per-shard query counts reveal little [3].

Several works in this context also study infinitely divisible count-noise laws, which can be generated in a distributed way by summing independent contributions from many users. In particular, our use of negative-binomial distributions is inspired by Ghazi et al. [28].

One-sided noise. Optimal non-negative noise for a single sensitivity-one release is well understood: Case et al. [12] analyze simple families such as the truncated geometric, negative binomial and Poisson padding. Xiao et al. [43] show that the $\Theta\left(\frac{1}{\epsilon}\log\frac{1}{\delta}\right)$ mean error achieved by a clamped two-sided geometric distribution is the minimum possible. For repeated releases Xiao et al. [43] develop a hybrid Rényi analysis and a convex program for composition-optimal one-sided noise. Our experiments include this noise and show that the negative binomial, which can be generated in a distributed setting, achieves comparable privacy guarantees.

Definitions

We write $[t] := \{1, \ldots, t\}$ and $\mathbb{Z}_{+} := \{0, 1, 2, \ldots\}$.

We describe privacy guarantees in terms of the privacy loss random variable [18] and the closely related hockey-stick privacy profile [6]. Given two distributions $P$, $Q$, the privacy loss random variable $L_{P,Q}$ is defined by $\ell(\omega; P, Q) := \ln\left(\frac{P(\omega)}{Q(\omega)}\right)$ where $\omega\sim P$. We refer to its distribution as the privacy loss distribution (PLD). For $\kappa\ge0$, the $\kappa$-hockey-stick divergence between two distributions $P$, $Q$ is defined as

where $[x]_{+} := \max\{0,x\}$ [5].

The dataset adjacency notions we consider are the standard add/remove and zero-out notions. In add/remove adjacency datasets $S, S' \in\mathcal{X}^{*}$ are adjacent if $S$ can be obtained from $S'$ via adding or removing a single element. For the zero-out notion, datasets $S, S' \in\mathcal{X}^{*}$ are adjacent if $S$ can be obtained from $S'$ by replacing a single element with the “zero” element $\bot$ which we assume to be in $\mathcal{X}$. In the common application of aggregation this element is just $0$ (or the zero vector).

Given an algorithm $M : \mathcal{X}^{*} \to\mathcal{Y}$, its privacy profile $\delta_M : \mathbb{R} \to[0,1]$ is defined as $\delta_M(\varepsilon) := \sup_{S,S'} H_{e^\varepsilon}(M(S) \mathbin{\|} M(S'))$, where the supremum is over all pairs of adjacent datasets. Since the hockey-stick divergence is asymmetric in general, we write $\vec{\delta}_M$ for the supremum restricted to the remove direction, in which $S'$ is obtained from $S$ by removing an element or replacing it with $\bot$, and $\overleftarrow{\delta}_M$ for the add direction, in which $S$ is obtained from $S'$ in this way. Consequently, $\delta_M(\varepsilon) = \max\{\vec{\delta}_M(\varepsilon),\overleftarrow{\delta}_M(\varepsilon)\}$. Given $\varepsilon> 0$, $\delta\in[0,1]$, an algorithm $M$ will be called $(\varepsilon,\delta)$-differentially private (DP) if $\delta_M(\varepsilon) \le\delta$ [21].

A key concept for characterizing the privacy guarantees of an algorithm is that of a dominating pair of distributions [44]. Given distributions $P_1$, $Q_1$, $P_2$, $Q_2$, we say that a pair of distributions $(P_1,Q_1)$ dominates the pair of distributions $(P_2,Q_2)$ if for all $\kappa\ge0$ we have $H_{\kappa}(P_2 \mathbin{\|} Q_2) \le H_{\kappa}(P_1 \mathbin{\|} Q_1)$. If $\vec{\delta}_M(\varepsilon) \le H_{e^\varepsilon}(P \mathbin{\|} Q)$ for every $\varepsilon\in\mathbb{R}$, we call $(P,Q)$ a remove-direction dominating pair for $M$. The swapped pair controls the add direction: $\overleftarrow{\delta}_M(\varepsilon) \le H_{e^\varepsilon}(Q \mathbin{\|} P)$ for every $\varepsilon\in\mathbb{R}$ [44]. This “swap” fact, which we use repeatedly, relies on domination at all $\kappa\ge0$: it follows from the identity $H_{\kappa}(Q \mathbin{\|} P) = \kappa H_{1/\kappa}(P \mathbin{\|} Q) + 1 - \kappa$, valid for all distributions $P,Q$ and all $\kappa> 0$.