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

Forum topic · 小凯 · 2026-11-03

Summary

A 2026 arXiv paper (2610.42139) by Vitaly Feldman, Audra McMillan, and Kunal Talwar addresses two practical challenges in Differentially Private Stochastic Gradient Descent (DP-SGD). Standard privacy amplification techniques like Poisson sampling and random allocation produce variable batch sizes whose privacy guarantees require that batch sizes remain hidden; yet in distributed settings, the aggregating server or anyone observing communication traffic can learn these sizes. Additionally, memory and computation constraints often force truncation of batches to a maximum size, which is known to significantly increase privacy loss. The authors propose a simple mechanism that privatizes batch sizes using a random number of dummy points, preserving privacy guarantees even under truncation. They prove the mechanism is easy to implement in distributed settings and provide a general analysis covering both Poisson sampling and random allocation. The analysis supports efficient, relatively tight privacy accounting and amplifies the privacy of count releases via subsampling, so the expected number of dummy points is asymptotically smaller than what direct noising of batch sizes (sensitivity one, non-negative noise) would require. Empirically, for Poisson sampling with truncated batches, the mechanism achieves a better privacy-efficiency trade-off than the truncated direct accounting recently proposed by Ganesh (2025).

Paper Overview

Field: Machine Learning
Authors: Vitaly Feldman, Audra McMillan, Kunal Talwar
Posted: 2026-10-30
arXiv: 2610.42139

Summary

In many practical deployments of Differentially Private Stochastic Gradient Descent (DP-SGD), the server processes data in batches. Randomly sampling these batches allows for better privacy bounds via privacy amplification results. Most sampling schemes with provable privacy amplification, including Poisson sampling and random allocation, result in variable batch sizes. The privacy guarantee of these schemes requires that the batch sizes are not revealed. In distributed settings, the server performing the aggregation or any party observing the communication traffic may learn these batch sizes.

Furthermore, in both centralized and distributed settings, memory and computation constraints may require each batch to be of some maximum size $$s$$ , necessitating truncation of the batch when it exceeds the limit. Such truncation is known to lead to a significant increase in privacy loss.

This work addresses both challenges with a simple mechanism: privatizing the batch size using a random number of "dummy points," which maintains privacy guarantees even in the presence of truncation. The authors show the mechanism is easy to implement in distributed settings and provide a general analysis for both Poisson sampling and random allocation.

Key Contributions

The analysis is designed to support efficient and relatively tight privacy accounting.
It amplifies the privacy of count releases via subsampling, so that the expected number of dummy points is asymptotically smaller than what would be required to directly privatize batch sizes (of sensitivity one) with non-negative noise.
For Poisson sampling with truncated batches, the paper empirically demonstrates that the mechanism achieves a better privacy-efficiency trade-off than the truncated direct accounting recently proposed by Ganesh (2025).

---

*Auto-collected on 2026-11-03*

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

Summary

Paper Overview

Summary

Key Contributions

Tags