Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
Pujol and Desfontaines investigate the potential for private histograms to leverage increased error tolerance in larger groups to enhance privacy protections for their members. They establish a count-dependent form of zero-concentrated differential privacy (zCDP) that balances privacy budget and utility, revealing that the optimal privacy budget scales as \( v(n) = O_r(n^{-2}) \) for larger groups. Their findings demonstrate that while maintaining strict utility requirements, the inverse-square rate of privacy loss is optimal, offering significant insights into privacy mechanisms for disjoint groups.
Larger groups can achieve stronger privacy guarantees by allowing more error, with an optimal inverse-square rate of privacy loss.
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\'enyi-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 $\mathbb{E}\lvert\widehat{x}_i-x_i\rvert<r\max\{x_i,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 shifted-log Gaussian mechanism has a certified budget $v(n)=O_r(n^{-2})$. Conversely, for every fixed $0<r<1$, any mechanism satisfying the same positive-count utility requirement and count-dependent zCDP must have $v(n)=\Omega_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 $\pi/(4e^2)$ and $1/\pi$, a factor below three. At $r=1$, a data-independent release meets the repaired criterion with zero privacy loss.