Better Privacy Guarantees for Larger Groups Jack Fitzsimons Oblivious [email protected]
July 15, 2026
arXiv:2607.14406v1 [cs.CR] 15 Jul 2026
Abstract Pujol and Desfontaines asked whether a private histogram can allow more error on larger counts and use that slack to protect members of larger groups more strongly. We study this question for fixed disjoint groups under add-or-remove-one adjacency. The privacy budget v(n) depends on the affected count, is nonincreasing, and must bound both Rényi-divergence directions at every order. This is the count-dependent form of zero-concentrated differential privacy (zCDP) studied here. The original strict relative-error condition is impossible at count zero. We therefore make the boundary tolerance explicit by requiring E|b xi − xi | < r max{xi , 1}, without changing the requirement at any positive count. Our main result determines the best dependence on group size. For the upper bound, we directly specialize an existing shifted-transformation framework. The resulting shiftedlog Gaussian mechanism has a certified budget v(n) = Or (n−2 ). Conversely, for every fixed 0 < r < 1, any mechanism satisfying the same positive-count utility requirement and countdependent zCDP must have v(n) = Ωr (n−2 ). Thus the inverse-square rate is optimal under the repaired formulation. A many-count information argument further places the leading coefficient in the large-count-then-small-error limit between π/(4e2 ) and 1/π, a factor below three. At r = 1, a data-independent release meets the repaired criterion with zero privacy loss.
1
The problem, its boundary, and the main result
Suppose a dataset is split into fixed, disjoint groups, and let xi be the number of records in group i. A standard private histogram adds noise of roughly the same size to every count. That gives every person roughly the same privacy guarantee, but it gives a large group much smaller relative error than a small group. Pujol and Desfontaines [2023] asked whether one can spend this surplus accuracy differently: allow the error in group i to grow in proportion to xi , and use the extra noise to protect people in larger groups more strongly. Their definition asks for a privacy budget that depends only on the group count and does not increase as the count grows. The result has two halves: a construction with an inverse-square privacy budget, and a construction-independent proof that no mechanism satisfying the same requirements can improve that rate. Theorem 1.1 (Optimal group-size rate). For every fixed 0 < r < 1, the repaired formulation in (2) and definition 2.1 admits a mechanism with a finite nonincreasing budget v(n) = Θr (n−2 ). 1
Conversely, every mechanism satisfying the positive-count utility requirement and count-dependent group-wise zCDP with a finite nonincreasing budget obeys lim inf n2 v(n) ≥ n→∞
(1 − r)6 > 0. 128r2 (1 + r)2
Hence no mechanism satisfying these requirements can make the positive-count budget decay asymptotically faster than the inverse-square rate achieved by the construction. At r = 1, the repaired formulation admits a data-independent release with v ≡ 0. Proof. For the upper bound, take, for example, r0 = r/2 and c = 1 in theorem 3.1. The converse is proposition 6.2, and the endpoint is proposition 2.3. For the feasibility half, the key change of coordinates is simple. Upper-bound intuition. A one-person change is additive in count space but becomes smaller in log space: 1 log(n + 1 + c) − log(n + c) = log 1 + n+c
≍
1 . n
Add fixed-variance Gaussian noise in log space. Gaussian zCDP is quadratic in the change of the mean, so the privacy budget is of order 1/n2 . The converse starts from the opposite observation. Accuracy makes nearby counts distinguishable, while privacy limits how distinguishable they can be. A two-count test determines the exponent. Using many counts at once gives the sharper constant.
1.1
Contributions and relation to prior work
Table 1 separates the inherited ingredients from the arguments developed here. The lower bounds do not assume the upper construction, and we are not aware of an earlier lower bound for this formulation. The closest upper-bound ingredient is Finley et al. [2026]. Their template computes f (q(D) + a), adds fixed-variance Gaussian noise, and applies an estimator g. With q(D) = n,
a = c,
f (x) = log x,
2
g(y) = ey−σ − c
it gives the unprojected mechanism studied here. Finley et al.’s mean-unbiased estimator uses the familiar drift −σ 2 /2. We use −σ 2 because it minimizes expected absolute multiplicative error. Their analysis already contains the exact gap between adjacent transformed queries. Their stated PRzCDP policy replaces this gap by a worst case over the baseline query value. For a unit count record, that worst case is the boundary cost log2 ((1 + c)/c)/(2σ 2 ). Here the budget is meant to vary with the current count, so we keep the exact adjacent gap. This gives (6). Related work allows privacy guarantees to depend on an individual’s data or on a public policy function [Lui and Pass, 2015, Seeman et al., 2024]. The relative Gaussian mechanism gives Rényi-DP bounds for output-dependent Gaussian variance under relative sensitivity in a broader setting [Hendrikx et al., 2024]. These works provide broader forms of data-dependent privacy, but they do not by themselves give the count-local feasibility and mechanism-independent converse proved here.
2
Ingredient
Source
Role in the solution
Problem and privacy target
Pujol and Desfontaines [2023] define group-wise zCDP and ask for a count-only, nonincreasing privacy budget under relative expected error.
We keep their bidirectional, all-orders definition, prove that the literal zero-count utility condition is impossible, and state a zero-tolerant repair.
Relative and multiplicative error
Xiao et al. [2011] study relative-error-aware mechanisms; Le Ny and Pappas [2013] study multiplicative log-Laplace and lognormal mechanisms.
These works motivate measuring error relatively and moving from count space to log space.
Shifted transformation mechanism
Finley et al. [2026] add Gaussian noise after a concave transform, including f (x) = log x with a positive offset, building on the PRzCDP framework of Seeman et al. [2024].
We specialize that template to a count, choose the inverse drift for expected absolute error, and interpret the exact adjacent gap already present in their analysis as the count-local budget required here.
The n−2 scale
Azize [2023] studies N (n, r2 n2 ) and, in a one-sided calculation, exposes an n−2 term for this larger-groups question.
We identify the reverse high-order divergence obstruction and use an equal-variance log representation to obtain finite zCDP in both directions at every order.
Optimality
Bun and Steinke [2016] give the Gaussian zCDP calculation and the quadratic group-privacy rule.
For every fixed 0 < r < 1, we combine these tools with two-count and many-count testing arguments to prove that no mechanism satisfying the positive-count formulation can improve the n−2 exponent.
Table 1: Prior results and new arguments used to establish feasibility and, for every fixed 0 < r < 1, the optimal positive-count rate for the repaired formulation. Relative error also appears in private hierarchical counting. Biswas et al. [2024] exploit tree structure to estimate hierarchical heavy hitters under a single global differential-privacy guarantee. That setting is complementary: the groups overlap along a hierarchy, whereas the present question concerns fixed disjoint groups and asks for the privacy budget itself to improve with the affected count.
1.2
Scope
The upper and lower bounds match in asymptotic order. They do not identify a pointwise-optimal budget or the exact small-error coefficient. The lower bound uses utility only at positive counts, so the choice made at zero does not affect the optimal exponent. We also follow the alternative path suggested by Pujol and Desfontaines: this paper constructs a different mechanism rather than analyzing their randomized Algorithm 1.
3
2
The formal problem and the necessary zero-count repair
Let a data universe U be partitioned into fixed disjoint groups U1 , . . . , Uk . A dataset D is a finite multiset of records. Write x(D) = (x1 (D), . . . , xk (D)), where xi (D) is the number of records from Ui . Two datasets are neighbors if one is obtained from the other by adding or removing one record. Each neighboring edge joins two consecutive counts. We index the edge by its larger count and use one budget to bound both Rényi-divergence directions. Definition 2.1 (Count-dependent group-wise zCDP). Let v : Z≥0 → R≥0 be nonincreasing. For neighboring datasets D, D′ that differ by one record from group i, define ni (D, D′ ) = max{xi (D), xi (D′ )}. A mechanism M satisfies count-dependent v-group-wise zCDP if, for every such pair and every α > 1, max Dα M(D) ∥ M(D′ ) , Dα M(D′ ) ∥ M(D) ≤ αv ni (D, D′ ) . This is equivalent to applying the ordered-pair condition of Pujol and Desfontaines [2023] to both orderings of every neighboring pair. On an edge joining n and n + 1, the two orderings invoke v(n) and v(n + 1); both divergences must therefore obey α min{v(n), v(n + 1)} = αv(n + 1), because v is nonincreasing. Thus definition 2.1 states exactly the original two ordered-pair requirements, not a stronger substitute. The adjective “group-wise” follows the terminology of the open problem and refers to histogram cells. Later, “group privacy” refers to the standard chaining guarantee for changing several records; the two uses are distinct. Throughout the paper, all logarithms are natural. The utility requirement in the open problem is bi − xi | < rxi E|x
for every group i.
(1)
At xi = 0, the right-hand side is zero. Proposition 2.2 (Why the literal statement cannot include zero). No random variable can satisfy (1) when xi = 0. Moreover, for 0 < r < 1, replacing the strict inequality by a weak one does not repair the problem if one also asks for finite two-sided Rényi divergence across the edge 0 ↔ 1. bi | < 0, which is impossible. Proof. At count zero, (1) asks for E|x bi | ≤ 0 forces the affected released coordinate at count Now replace < by ≤. The condition E|x zero to equal zero almost surely. Call this marginal law P0 = δ0 . By data processing, finite Rényi divergence of the full output laws implies finite divergence of these coordinate marginals. If Dα (P1 ∥P0 ) is finite for any α > 1, then P1 must be absolutely continuous with respect to P0 , and hence P1 = δ0 as well. Its expected error at count one is therefore 1, which is larger than r when r < 1.
4
There are two natural repairs. One may ask only about positive counts, or one may allow a fixed absolute tolerance at zero. We use the second form: bi − xi | < r max{xi , 1}. E|x
(2)
For every nonempty group, this is exactly the original relative-error target. The value at zero merely makes the target compatible with privacy across the first adjacency edge. Proposition 2.3 (The trivial endpoint). When r = 1, the data-independent real-valued release bi = 1/2 satisfies (2) strictly at every count n ≥ 0 and has v ≡ 0. Hence 0 < r < 1 is the nontrivial x regime. Proof. At n = 0, the absolute error is 1/2 < 1, while at every n ≥ 1 it is n − 1/2 < n. Because the output law does not depend on the dataset, every Rényi divergence is zero.
3
Feasibility via a count-local shifted transformation
Fix the requested tolerance r ∈ (0, 1]. Choose two design parameters: 0 < r0 < r
and
c > 0.
Choose r0 < r so that the final utility bound is strict; r0 may be arbitrarily close to r. Let Φ be the standard normal cumulative distribution function, and set σ=Φ
−1
1 r0 + . 2 2(1 + c)
(3)
The argument of Φ−1 lies strictly between 1/2 and 1, so σ is positive and finite. For each group i, independently sample Zi ∼ N (0, 1) and release h
bi = (xi + c) exp(σZi − σ 2 ) − c x
i +
.
(4)
Here [y]+ = max{y, 0}. The mechanism has three steps: 1. start from the shifted log-count log(xi + c); 2. add Gaussian noise σZi and the deterministic drift −σ 2 ; 3. exponentiate, subtract c, and clip at zero. The shift c makes the logarithm well-defined at zero. The drift −σ 2 is not the familiar meancorrection −σ 2 /2. It is the drift that minimizes expected absolute multiplicative error; section 4 makes this precise. Theorem 3.1 (Mechanism and a closed-form privacy budget). The mechanism in (4) has the following properties. (i) For every group and every count n ≥ 0, bi − n| ≤ E|x
r0 (n + c) < r max{n, 1}. 1+c 5
(ii) It satisfies count-dependent group-wise zCDP with 1+c 1 , v(0) = v(1) = 2 log2 2σ c
(5)
1 n+c . log2 2 2σ n−1+c
(6)
and, for n ≥ 1,
v(n) =
The function v is nonincreasing. Definition 2.1 never invokes v(0), because every neighboring edge has maximum endpoint at least 1; setting v(0) = v(1) merely defines v on all nonnegative integers while preserving monotonicity. (iii) As n → ∞, v(n) =
1 + O(n−3 ). 2σ 2 n2
(7)
A one-person change near count n changes the log-count by about 1/n. Gaussian zCDP cost is quadratic in this mean shift, which yields the 1/n2 rate. Sections 4 and 5 verify the utility and privacy claims. Corollary 3.2 (A simple default shift). Taking c = 1 gives σ = Φ−1 and v(0) = v(1) =
log2 2 , 2σ 2
1 r0 + 2 4
v(n) =
log2 (1 + 1/n) 2σ 2
(n ≥ 1).
The mechanism releases nonnegative real numbers. If integer counts are preferred, use stochastic rounding: for y ≥ 0, output ⌊y⌋ or ⌈y⌉ with probabilities chosen so that the conditional mean is y. This is postprocessing, so it cannot worsen privacy. Moreover, because the true count n is an integer and z 7→ |z − n| is linear between consecutive integers, the conditional expected error after rounding is exactly |y − n|.
4
Exact pre-clipping utility calibration
The utility proof uses the following shifted-lognormal identity. Lemma 4.1 (Exact absolute multiplicative error). If Z ∼ N (0, 1) and σ > 0, then E exp(σZ − σ 2 ) − 1 = 2Φ(σ) − 1. Proof. The factor exp(σZ − σ 2 ) crosses one at Z = σ. We use the Gaussian identity 2
2
eσz−σ φ(z) = e−σ /2 φ(z − σ), where φ is the standard normal density. It gives h i 1 2 2 E eσZ−σ 1{Z ≤ σ} = e−σ /2 2
6
(8)
and the same value on the event Z > σ. Splitting the absolute value at Z = σ, these two weighted terms cancel: h
2
i
2
E eσZ−σ − 1 = E (1 − eσZ−σ )1{Z ≤ σ} h
2
+ E (eσZ−σ − 1)1{Z > σ} = Φ(σ) − 1 − Φ(σ)
i
= 2Φ(σ) − 1.
Let 2
Un = (n + c)eσZ−σ − c be the output before clipping. Then
2
Un − n = (n + c) eσZ−σ − 1 . By lemma 4.1 and the definition of σ, E|Un − n| = (n + c) 2Φ(σ) − 1 r0 . = (n + c) 1+c
(9)
Clipping at zero cannot increase the distance to any n ≥ 0, so (9) is also an upper bound for the released value. For n ≥ 1, n+c ≤ n, 1+c so the expected error is at most r0 n < rn. At n = 0, it is at most cr0 /(1 + c) < r. This proves part (i) of theorem 3.1.
4.1
Why the drift is −σ 2
For a fixed noise level σ, consider the more general factor eσZ−a . Dominated convergence justifies differentiating under the expectation on every compact interval of a. Away from a probability-zero threshold, h i h i d E|eσZ−a − 1| = E eσZ−a 1{Z ≤ a/σ} − E eσZ−a 1{Z > a/σ} da 2 = eσ /2−a (2Φ(a/σ − σ) − 1) .
This derivative is negative for a < σ 2 , zero at a = σ 2 , and positive afterward. Thus a = σ 2 is the unique minimizer of expected absolute multiplicative error. By contrast, a = σ 2 /2 makes the multiplicative factor have mean one. The two objectives are different because a lognormal distribution has a long right tail.
7
5
Exact divergence before postprocessing
For the unprojected output Un , the inequality Un + c > 0 holds almost surely, so log(Un + c) = log(n + c) − σ 2 + σZ.
(10)
Thus, after the bijective transformation u 7→ log(u + c), the output law is the Gaussian N log(n + c) − σ 2 , σ 2 .
Because the variance is independent of n, every adjacent pair has finite Rényi divergence at all orders. For equal-variance Gaussians, the Rényi divergence is exact [Bun and Steinke, 2016, Lemma 2.4]: Dα N (µ, σ 2 ) ∥ N (ν, σ 2 ) =
α(µ − ν)2 . 2σ 2
(11)
Rényi divergence is invariant under a measurable bijection and obeys data processing [van Erven and Harremoøs, 2014]. Applying (11) to (10) gives, for any counts n, m ≥ 0, α n+c log2 . 2 2σ m+c
Dα (Un ∥Um ) = Dα (Um ∥Un ) =
(12)
Clipping and optional stochastic rounding are postprocessing, so the same expression remains a valid upper bound for the released estimate. For the adjacent unprojected edge n − 1 ↔ n, equation (12) is exactly αv(n) with v(n) from (6), in both directions. After clipping and optional rounding, data processing gives the corresponding upper bound. The boundary edge 0 ↔ 1 uses v(1), because its larger endpoint is 1; the chosen extension v(0) = v(1) is not invoked. Thus the released mechanism satisfies definition 2.1. The monotonicity is immediate from n+c log n−1+c
1 = log 1 + , n−1+c
which decreases with n. Finally, a Taylor expansion gives 1 log 1 + n−1+c
=
1 + O(n−2 ), n
and hence (7). For the full histogram, neighboring datasets change only one coordinate. All other coordinate laws are identical, and independent product factors with identical laws contribute zero Rényi divergence. Therefore the product argument proves part (ii) of theorem 3.1; part (iii) follows from the scalar formula (6) and its expansion above.
5.1
Interpreting the rate
A zCDP guarantee ρ implies q
ρ + 2 ρ log(1/δ), δ -DP for every δ > 0 [Bun and Steinke, 2016]. Thus, for the mechanism above, v(n) = Θ(n−2 ) corresponds, for fixed δ, to an ordinary approximate-DP epsilon of order 1/n in the regime where the square-root term dominates. 8
The parameter c controls a boundary tradeoff. Smaller c permits a larger σ for the same error and therefore improves the large-n constant. But it makes the jump from 0 to 1 larger in log space, so v(0) = v(1) worsens. The choice c = 1 in corollary 3.2 is a simple default rather than a universal optimum. Two limit regimes make this tradeoff precise. First fix c > 0, let n → ∞, and then let r ↓ 0 while r0 /r → 1. Then r r π (1 + c)2 σ∼ , lim lim r2 n2 v(n) = , r↓0 n→∞ 1+c 2 π whereas the boundary cost satisfies (1 + c)2 1+c v(1) ∼ log2 . 2 πr c
Thus c = 1 has large-count coefficient 4/π. Taking c ↓ 0 approaches 1/π, but the first-edge budget diverges. For example, the diagonal choice c = r used below has v(1) of order r−2 log2 (1/r). Second fix 0 < r < 1, let r0 ↑ r, and let c ↓ 0. The leading large-count coefficient approaches 1 2 Φ−1 ((1 + r)/2)2
.
For small r, Φ
−1
r
((1 + r)/2) = r
π + O(r3 ), 2
so the large-count budget approaches 1 . (13) πr2 n2 This is an iterated limit: first n → ∞, then r0 ↑ r and c ↓ 0, and finally r ↓ 0. The coefficient is approached within the allowed family. No fixed choice with r0 < r and c > 0 need attain it, and we do not claim that it is exactly optimal. v(n) ∼
6
Mechanism-independent lower bounds: two counts, then many
The upper construction alone does not show whether the inverse-square rate is intrinsic. The lower bounds below show that it is. They apply to arbitrary mechanisms, including mechanisms with correlated coordinates, multiple noise stages, or output laws without densities. For a vector release, postprocessing to one coordinate preserves the utility assumption and cannot increase the privacy loss. We state utility in this section with the weak inequality Em |Y − m| ≤ rm. This enlarges the admissible class, so every lower bound below also applies to the manuscript’s strict positive-count criterion. Testing two counts proves the exponent for every fixed 0 < r < 1. Testing many counts also uses accuracy at the intermediate values and yields a stronger small-error constant. The one-line lower-bound idea. Choose a hidden offset J, so the true count is n + J. Accuracy says the release must reveal information about J. Privacy says it cannot reveal too much. Comparing the two statements forces a lower bound on v(n).
9
For a discrete random variable J, write H(J) for its Shannon entropy. The following pathwise lemma replaces the varying edge budgets along a fixed chain by their common upper bound. Lemma 6.1 (Pathwise zCDP group privacy). Let D0 , . . . , Dk be a fixed chain of datasets such that consecutive datasets are neighbors. Suppose that every edge of this chain satisfies ρ-zCDP in both directions. If Pj is the output law on Dj , then, for every α > 1, max{Dα (P0 ∥Pk ), Dα (Pk ∥P0 )} ≤ αk 2 ρ. Proof. This is the standard quadratic group-privacy theorem for zCDP [Bun and Steinke, 2016, Proposition 1.9], applied to the fixed chain D0 , . . . , Dk . Its proof uses only the zCDP inequalities for consecutive laws on that chain, so no global uniform bound outside the path is required.
6.1
A two-count rate bound
The two-count argument proves the exponent for every 0 < r < 1. The later many-count argument improves the constant as r ↓ 0. Proposition 6.2 (Rate lower bound for 0 < r < 1). Fix 0 < r < 1. Write Em for expectation when the affected-group count is m. Suppose a mechanism produces an estimate Y with Em |Y − m| ≤ rm
for every positive count m,
and satisfies count-dependent group-wise zCDP for a finite, nonincreasing function v. Define
Cr =
1 + 3r 1−r
2
.
Then, for every n ≥ 1, v(n) ≥
(1 − r)2
2 .
(14)
2 ⌈Cr n⌉ − n
Consequently, lim inf n2 v(n) ≥ n→∞
(1 − r)6 , 128r2 (1 + r)2
(15)
so v(n) = Ωr (n−2 ). Proof. Fix n and put m = ⌈Cr n⌉,
q=
q
m/n,
t=
√
mn = nq.
Let Pn and Pm be the output laws on nested datasets with affected-group counts n and m. Utility first separates these laws; privacy will then limit that separation. The finite expected absolute-error bounds make the relevant deviations integrable, so Markov’s inequality gives Pn (Y > t) ≤
rn , t−n
Pm (Y ≤ t) ≤
Since m = nq 2 , the sum of these two bounds is r
q+1 . q−1 10
rm . m−t
The definition of Cr ensures q ≥ (1 + 3r)/(1 − r), so this sum is at most (1 + r)/2. For A = {Y ≤ t}, dTV (Pn , Pm ) ≥ Pn (A) − Pm (A) ≥
1−r . 2
(16)
Every one-person edge on the path from count n to count m has budget at most v(n). Applying lemma 6.1 with ρ = v(n) therefore gives, for every α > 1, Dα (Pn ∥Pm ) ≤ α(m − n)2 v(n). Using the limit of Rényi divergence to KL divergence as α ↓ 1 [van Erven and Harremoøs, 2014] gives DKL (Pn ∥Pm ) ≤ (m − n)2 v(n). Pinsker’s inequality and (16) give DKL (Pn ∥Pm ) ≥ 2dTV (Pn , Pm )2 ≥
(1 − r)2 . 2
Combining the last two displays proves (14). Finally, Cr − 1 =
8r(1 + r) , (1 − r)2
which gives (15) after multiplying by n2 and taking n → ∞.
6.2
Absolute error forces information
The following lemma converts expected absolute estimation error into mutual information. Its 1/4 term is the mean absolute value of an independent uniform dither on [−1/2, 1/2]. Lemma 6.3 (Absolute error forces information). Let J be an integer-valued random variable with e ) be any real-valued estimator. finite support, let Y take values in a standard Borel space, and let J(Y If e )|, D = E|J − J(Y then
I(J; Y ) ≥ H(J) − log 2e D +
1 4
.
(17)
Proof. Let U be independent of (J, Y ) and uniform on [−1/2, 1/2], and set X = J + U . The unit intervals around distinct integers overlap only at endpoints. Thus h(X) = H(J). Conditional on Y = y, the law of X is a mixture of uniform densities on those disjoint intervals, with weights Pr(J = j | Y = y). Each component has differential entropy zero because its interval has length one. Therefore h(X | Y = y) = H(J | Y = y) for almost every y, and hence I(X; Y ) = I(J; Y ) [Cover and Thomas, 2006]. Use the same estimator for X. By the triangle inequality, e )| ≤ D + E|U | = D + 1 . E|X − J(Y 4
11
A real random variable W with E|W | ≤ d has differential entropy at most log(2ed); the centered Laplace law is the maximizer [Cover and Thomas, 2006]. This follows by comparing the density of W with (2d)−1 e−|w|/d and using nonnegativity of Kullback-Leibler divergence. Because Y is standard Borel, regular conditional laws exist. For almost every y, define h
i
e d(y) = E X − J(y) Y =y .
The entropy bound gives h(X | Y = y) ≤ log(2e d(y)). Averaging over y and applying Jensen’s inequality gives e )| . h(X | Y ) ≤ log 2e E|X − J(Y Hence I(J; Y ) = I(X; Y ) = h(X) − h(X | Y ), which is exactly (17).
6.3
The general many-count inequality
Theorem 6.4 (Many-count inequality for privacy and utility). Fix 0 < r < 1. Write Em for expectation when the affected-group count is m. Suppose a mechanism produces an estimate Y such that, at every positive count m, Em |Y − m| ≤ rm. (18) Suppose also that it satisfies count-dependent group-wise zCDP for a finite, nonincreasing function v. Fix a base count n ≥ 1. Let J be any finitely supported random variable on the nonnegative integers, and let j⋆ be any nonnegative integer with E(J − j⋆ )2 > 0. Then h
v(n) ≥
H(J) − log 2e r(n + EJ) + 14 E(J − j⋆ )2
i +
.
(19)
Proof. Fix a nested sequence of datasets D0 , D1 , . . . in which Dj has affected-group count n + j and each step adds one record from that group. Choose the hidden offset J, run the mechanism on DJ , and call the relevant released estimate Y . Let Pj be its law on Dj , and use Pj⋆ as a reference law. The proof has two parts. Privacy upper-bounds I(J; Y ); utility lower-bounds it. Every count on the path from n + j to n + j⋆ is at least n. Since v is nonincreasing, every one-person edge on that path has zCDP budget at most v(n). With k = |j − j⋆ |, lemma 6.1 gives, for every α > 1, Dα (Pj ∥Pj⋆ ) ≤ αk 2 v(n). Using the limit of Rényi divergence to KL divergence as α ↓ 1 [van Erven and Harremoøs, 2014] gives DKL (Pj ∥Pj⋆ ) ≤ (j − j⋆ )2 v(n). (20) P
Let P = j Pr(J = j)Pj be the mixture law of Y . Averaging (20) over J and using the standard mutual-information/relative-entropy identity [Cover and Thomas, 2006] gives, for every reference law Q, EJ DKL (PJ ∥Q) = I(J; Y ) + DKL (P ∥Q). Taking Q = Pj⋆ and dropping the final nonnegative term yields I(J; Y ) ≤ v(n)E(J − j⋆ )2 . 12
(21)
e ) = Y − n, Now use utility. With the estimator J(Y
E|J − (Y − n)| = E|(n + J) − Y | ≤ rE(n + J) = r(n + EJ). By lemma 6.3, 1 I(J; Y ) ≥ H(J) − log 2e r(n + EJ) + 4
.
(22)
Combining (21) and (22) gives the stated ratio when its numerator is positive. If the numerator is negative, the bound is vacuous; since v(n) ≥ 0, the positive part covers both cases. Equation (19) displays three competing quantities. The entropy H(J) strengthens the information lower bound. The mean EJ enlarges the allowed error, and E(J − j⋆ )2 is the privacy cost. A strong prior balances all three.
6.4
A fully explicit finite bound
The uniform distribution gives a clean formula with no limiting argument. Corollary 6.5 (Uniform many-count bound). Under the assumptions of theorem 6.4, let K ≥ 3 be odd. Then, for every n ≥ 1,
K 12 . log v(n) ≥ 2 K −1 2e r n + K−1 + 1 2
4
(23)
+
Proof. Take J uniform on {0, 1, . . . , K − 1} and set j⋆ = (K − 1)/2. Then H(J) = log K,
EJ =
K −1 , 2
E(J − j⋆ )2 =
K2 − 1 . 12
Substitute these three identities into (19). Fix r ∈ (0, 1) and a > 0, and choose odd integers Kn ≥ 3 such that Kn /(rn) → a. Then lim inf r2 n2 v(n) ≥ n→∞
12 a log . 2 a 2e(1 + ar/2) +
(24)
If we next let r ↓ 0, the right side is maximized at a = 2e3/2 and equals 3 ≈ 0.0746806. 2e3 The uniform-prior bound improves the two-count constant by a factor of 192/e3 ≈ 9.56.
13
(25)
6.5
A bell-shaped prior gives the sharper constant
The next construction uses a bell-shaped prior to increase entropy relative to squared spread. The following quantization lemma transfers this continuous-prior advantage to integer counts. Lemma 6.6 (Fine integer quantization). Let Z have a bounded, compactly supported, piecewisecontinuous density f . Let QS be SZ rounded to the nearest integer, with either convention at ties. As S → ∞, H(QS ) = log S + h(Z) + o(1),
(26)
EQS = SEZ + O(1),
(27)
EQ2S = S 2 EZ 2 + O(S).
(28)
Proof. For each quantization cell CS,k , let Z
fS (z) = S
f (u) du CS,k
(z ∈ CS,k ).
If pS,k = Pr(QS = k), then pS,k = fS (z)/S on that cell and hence H(QS ) − log S = −
Z
fS (z) log fS (z) dz.
Piecewise continuity gives fS → f almost everywhere. The functions fS are uniformly bounded and supported in a common compact enlargement of the support of f , so dominated convergence applied to t 7→ t log t proves (26). The pointwise bound |QS − SZ| ≤ 1/2 gives (27). Writing QS = SZ + ∆S with |∆S | ≤ 1/2, boundedness of Z gives 2SZ∆S + ∆2S = O(S) pointwise, which proves (28). Corollary 6.7 (Small-error lower-bound constant). For each r ∈ (0, 1), let a mechanism satisfy the assumptions of theorem 6.4, with budget vr . Then lim inf lim inf r2 n2 vr (n) ≥ r↓0
n→∞
π ≈ 0.1062921. 4e2
(29)
Proof. We take the limits in the order displayed in the result: first n → ∞, then r ↓ 0, and finally the truncation level L → ∞. Fix L > 0. Let ZL be a standard Gaussian conditioned on [−L, L], and write τL2 = Var(ZL ).
hL = h(ZL ),
The distribution is symmetric, so EZL = 0. Fix x > 0 and put S = xrn. Let QS be SZL rounded to the nearest integer, let B = ⌈LS⌉ + 1,
J = B + QS ,
j⋆ = B.
The shift B makes J nonnegative. By lemma 6.6, as n → ∞ with r, L, x fixed, H(J) = log S + hL + o(1), E(J − B)2 = S 2 τL2 + O(S), EJ = LS + o(S).
14
Apply theorem 6.4 and use S = xrn. Here log S = log(xrn), while the utility term inside the logarithm is 1 2e r(n + EJ) + = 2e rn 1 + Lxr + o(1) . 4 Thus the log(rn) terms cancel. After multiplying by r2 n2 and taking n → ∞, lim inf r2 n2 vr (n) ≥ n→∞
[log x + hL − log(2e) − log(1 + Lxr)]+ . x2 τL2
(30)
Now let r ↓ 0. For fixed L, optimize the right side over x. The optimum satisfies 1 log x + hL − log(2e) = . 2 Equivalently, x = xL = 2e3/2−hL , and the positive-part bracket equals 1/2. This gives lim inf lim inf r2 n2 vr (n) ≥ r↓0
n→∞
e2hL . 8e3 τL2
(31)
Finally let L → ∞. The truncated Gaussian converges to the standard Gaussian in entropy and variance: 1 hL → log(2πe), τL2 → 1. 2 Equation (31) therefore tends to 2πe π = 2. 8e3 4e The Gaussian is not an arbitrary guess. Within the continuous limiting-prior and scaleoptimization argument above, a limiting prior Z produces the factor e2h(Z) . 8e3 Var(Z) A Gaussian maximizes differential entropy at fixed variance [Cover and Thomas, 2006], so this quantity is at most π/(4e2 ). The truncated Gaussian sequence above reaches that limit. Thus Corollary 6.7 is optimal within this continuous-prior template; this observation does not rule out discrete, multiscale, or r-dependent uses of theorem 6.4. Call a family {(Mr , vr ) : 0 < r < 1} admissible if, for every r ∈ (0, 1), the mechanism Mr meets the positive-count utility condition Em |Y − m| ≤ rm for all m ≥ 1 and has a finite, nonincreasing count-dependent group-wise zCDP budget vr . For each such family, form the iterated leading coefficient lim inf lim inf r2 n2 vr (n). r↓0
n→∞
Let C⋆ be the infimum of this quantity over all admissible families. The upper construction and Corollary 6.7 give π 1 ≤ C⋆ ≤ . (32) 2 4e π For the upper bound, choose r0 (r) = r(1 − r) and c(r) = r for 0 < r < 1. This gives an admissible family. Since r0 (r)/r → 1 and c(r) → 0, (13) gives the coefficient 1/π. The ratio between the two displayed constants is 1/π 4e2 = ≈ 2.995. π/(4e2 ) π2 Thus the lower and upper bounds are now within a factor of three. 15
7
Why the unequal-variance Gaussian fails the definition
A tempting mechanism releases Xn ∼ N (n, r2 n2 ).
(33)
It has the right scale of expected error. Azize [2023] studies this deterministic-variance mechanism and derives a one-sided term proportional to α/(r2 n2 ), revealing the quadratic scale. The analysis below applies only to this mechanism, not to the randomized-variance Algorithm 1 of Pujol and Desfontaines [2023]. Unequal neighboring variances create a tail obstruction: one Rényi-divergence direction becomes infinite at sufficiently high orders. Lemma 7.1 (Finite Rényi divergence for unequal Gaussians). Let P = N (µP , s2P ) and Q = N (µQ , s2Q ) with positive variances. For α > 1, Dα (P ∥Q) is finite if and only if αs2Q + (1 − α)s2P > 0.
(34)
Proof. The defining integral for Rényi divergence is pα q 1−α . Its exponent is a quadratic polynomial in the integration variable. The coefficient of the negative quadratic term is R
1 2
α 1−α + 2 s2P sQ
!
.
The integral is finite exactly when this coefficient is positive. Multiplying by s2P s2Q gives (34). At equality the remaining exponential is nonintegrable as well. The boundary edge must be handled separately because X0 = N (0, 0) = δ0 , whereas lemma 7.1 assumes positive variances. Since the nondegenerate law X1 = N (1, r2 ) is not absolutely continuous with respect to X0 , Dα (X1 ∥X0 ) = ∞ for every α > 1. Thus the edge 0 ↔ 1 fails the required bound at every Rényi order. For a positive edge n ↔ n + 1 with n ≥ 1, apply the lemma to the reverse divergence from the larger-variance law at count n + 1 to the smaller-variance law at count n. It is finite only if αn2 + (1 − α)(n + 1)2 > 0, or equivalently (n + 1)2 . (35) 2n + 1 Consequently every positive edge has infinite reverse divergence at and above this finite threshold. The group-wise zCDP definition requires both directions for every α > 1, so (33) fails at the boundary for every order and on every positive edge above a finite order. Azize’s calculation identifies the correct n−2 scale, but an all-orders zCDP construction must avoid unequal neighboring variances. The shifted log-Gaussian mechanism does so: although its count-space variance changes with the count, every transformed law has variance σ 2 . The analysis of Pujol and Desfontaines’s Algorithm 1 remains open; the mechanism above proves feasibility without resolving it. α<
16
8
The remaining coefficient question
The inverse-square rate is now established for 0 < r < 1. One quantitative question remains: the exact value of the iterated coefficient C⋆ in (32). This section places the known bounds side by side and explains where further improvement would have to come from. Argument
Role
Small-r coefficient
Two-count proof using Markov and Pinsker Uniform many-count prior Truncated Gaussian prior Shifted log-Gaussian mechanism
lower bound lower bound lower bound upper bound
C⋆ ≥ 1/128 ≈ 0.00781 C⋆ ≥ 3/(2e3 ) ≈ 0.07468 C⋆ ≥ π/(4e2 ) ≈ 0.10629 C⋆ ≤ 1/π ≈ 0.31831
Table 2: Known small-r leading coefficients for the remaining coefficient question. The zero-count repair is part of the statement. The original strict relative-error requirement is logically impossible at zero. Equation (2) is a natural repair, not a consequence of the original wording. Readers interested only in nonempty groups may instead impose the original requirement for n ≥ 1; the same mechanism and proofs apply. Why the two-count proof stops at 1/128. Write m − n = arn and place a threshold at t = n + θ(m − n). In the small-r limit, Markov’s inequality and Pinsker’s inequality give at best 2 2 1 1 − . a2 aθ(1 − θ) +
This expression is maximized by θ = 1/2 and a = 8, giving exactly 1/128. Thus the threshold choices are optimal within the template using Markov’s inequality, one threshold, and Pinsker’s inequality. Proposition 6.2 keeps this argument because it proves the rate for every 0 < r < 1. The large constant improvement in Corollary 6.7 comes from changing the experiment: it uses many counts simultaneously. zCDP does not make the released count sub-Gaussian. The sub-Gaussian random variable in zCDP is the privacy loss, not the numerical output [Bun and Steinke, 2016]. A finite-support output distribution can have finite Rényi divergence at every order as long as neighboring laws have common support and bounded likelihood ratios. Therefore one cannot simply replace Markov’s inequality by a zCDP tail bound for |Y − n|. The useful coupling between privacy and utility is informational, as in Theorem 6.4. The remaining factor is below three. For small r, the shifted log-Gaussian mechanism approaches the upper constant 1/π ≈ 0.31831, while Corollary 6.7 gives π/(4e2 ) ≈ 0.10629. The ratio is about 2.995. After invoking zCDP’s quadratic group-privacy theorem, the information-radius step retains only the resulting KL endpoint bound. A sharper lower bound may need to exploit the higher Rényi orders more directly. The lognormal right tail is not the leading-order cost. For the asymptotically optimized p choice r0 /r → 1 and c → 0, small r gives σ = r π/2 (1 + o(1)) and 2
eσZ−σ − 1 = σZ + OL1 (σ 2 ). 17
So, to first order, the shifted log-Gaussian mechanism is simply additive Gaussian noise in count space. The skew appears only in higher-order terms. This suggests that merely correcting the visible right tail will not change the leading constant. A genuine improvement, if one exists, should change the local noise experiment. Recent work on exact zCDP characterizations of non-Gaussian mechanisms and direct optimization of noise laws under Rényi objectives provides tools for exploring that direction [Harrison and Manurangsi, 2025, Gilani et al., 2025]. The utility criterion is expected absolute error. The open problem asks for an expectation, and the mechanism is calibrated exactly for that objective. High-probability relative error, squared error, bias, and confidence intervals are different design criteria. The drift and the constants would change. The groups are fixed and disjoint. The proof uses the setting in the original problem: adding or removing one record changes one histogram coordinate. Overlapping or data-dependent groups require a separate sensitivity analysis. The mechanism is easy to compose. Because the guarantee is zCDP, repeated mechanisms P compose by adding their edge budgets pointwise: if release t has budget vt , then vtot (n) = t vt (n). The same statement holds for adaptive releases when each conditional mechanism satisfies its claimed edgewise bound uniformly over previous transcripts. This is one practical advantage of obtaining pure all-orders zCDP rather than a bound that is valid only up to a count-dependent Rényi order. The mechanism may be biased. The drift −σ 2 is chosen to minimize expected absolute error, not to make the estimate unbiased. For a counting release, bias can be reported or corrected only at the cost of changing the absolute-error calculation. The theorem makes no unbiasedness claim.
9
Conclusion
The original strict relative-error condition is impossible at count zero. After making that boundary tolerance explicit, the larger-groups question has a sharp answer at the level of asymptotic rate. Fix 0 < r < 1. Any mechanism satisfying the positive-count utility requirement and countdependent zCDP has v(n) = Ωr (n−2 ). The shifted log-Gaussian mechanism matches this bound with v(n) = Θr (n−2 ). The converse is mechanism-independent, so the inverse-square rate is not an artifact of the construction or of the zero-count repair. At r = 1, a data-independent release gives zero privacy loss. The upper construction is a count-local specialization of the transformation framework of Finley et al. [2026]. Their framework supplies the shifted transform and the exact transformed-query gap. We choose the inverse drift for expected absolute error, retain the count-specific gap, and verify bidirectional all-orders zCDP after postprocessing. The equal-variance log representation avoids the obstruction faced by the natural unequal-variance Gaussian, whose reverse divergence is infinite at high Rényi orders. The many-count argument narrows the remaining coefficient gap to π 1 ≤ C⋆ ≤ , 2 4e π and these bounds differ by less than a factor of three. Determining the exact value of C⋆ is the main question left open. 18
Acknowledgments. This note was prompted by the open problem of David Pujol and Damien Desfontaines. The author is grateful for the transformation-mechanism framework developed by Finley et al. and for Achraf Azize’s public 2023 calculations. The many-count lower bound grew out of asking where a two-count proof loses information.
References Achraf Azize. Open problem - better privacy guarantees for larger groups. Technical note, https://achraf-azize.github.io/Open_problem_Better_privacy_guarantees_for_ larger_groups.pdf, July 2023. Accessed July 14, 2026. Ari Biswas, Graham Cormode, Yaron Kanza, Divesh Srivastava, and Zhengyi Zhou. Differentially private hierarchical heavy hitters. Proceedings of the ACM on Management of Data, 2(5): 208:1–208:25, November 2024. doi: 10.1145/3695826. Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Martin Hirt and Adam Smith, editors, Theory of Cryptography, volume 9985 of Lecture Notes in Computer Science, pages 635–658. Springer, 2016. doi: 10.1007/978-3-662-53641-4_24. Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. John Wiley & Sons, Hoboken, NJ, 2nd edition, 2006. doi: 10.1002/047174882X. Brian Finley, Anthony M. Caruso, Justin C. Doty, Ashwin Machanavajjhala, Mikaela R. Meyer, David Pujol, William Sexton, and Zachary Terner. Slowly scaling per-record differential privacy. Journal of Privacy and Confidentiality, 16(1), April 2026. doi: 10.29012/jpc.992. Atefeh Gilani, Juan Felipe Gomez, Shahab Asoodeh, Flavio P. Calmon, Oliver Kosut, and Lalitha Sankar. Optimizing noise distributions for differential privacy. In Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pages 19505–19522. PMLR, 2025. URL https://proceedings.mlr.press/v267/gilani25a.html. Charlie Harrison and Pasin Manurangsi. Exact zCDP characterizations for fundamental differentially private mechanisms, October 2025. Hadrien Hendrikx, Paul Mangold, and Aurélien Bellet. The relative gaussian mechanism and its application to private gradient descent. In Sanjoy Dasgupta, Stephan Mandt, and Yingzhen Li, editors, Proceedings of the 27th International Conference on Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Research, pages 3079–3087. PMLR, 2024. URL https://proceedings.mlr.press/v238/hendrikx24a.html. Jérôme Le Ny and George J. Pappas. Privacy-preserving release of aggregate dynamic models. In Proceedings of the 2nd ACM International Conference on High Confidence Networked Systems, HiCoNS ’13, pages 49–56, New York, NY, USA, 2013. Association for Computing Machinery. doi: 10.1145/2461446.2461454. Edward Lui and Rafael Pass. Outlier privacy. In Yevgeniy Dodis and Jesper Buus Nielsen, editors, Theory of Cryptography, volume 9015 of Lecture Notes in Computer Science, pages 277–305. Springer, 2015. doi: 10.1007/978-3-662-46497-7_11. 19
David Pujol and Damien Desfontaines. Open problem - better privacy guarantees for larger groups. https://differentialprivacy.org/ open-problem-better-privacy-guarantees-for-larger-groups/, June 2023. Accessed July 14, 2026. Jeremy Seeman, William Sexton, David Pujol, and Ashwin Machanavajjhala. Privately answering queries on skewed data via per-record differential privacy. Proceedings of the VLDB Endowment, 17(11):3138–3150, 2024. doi: 10.14778/3681954.3681989. Tim van Erven and Peter Harremoøs. Rényi divergence and Kullback–Leibler divergence. IEEE Transactions on Information Theory, 60(7):3797–3820, July 2014. doi: 10.1109/TIT.2014.2320500. Xiaokui Xiao, Gabriel Bender, Michael Hay, and Johannes Gehrke. iReduct: Differential privacy with reduced relative errors. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data, pages 229–240. Association for Computing Machinery, 2011. doi: 10.1145/1989323.1989348.
20