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

The user wants me to convert a text into a semantic HTML fragment following specific rules. I need to analyze the original text and identify its structure. 1. Analyze the Original Text: * "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 this limit. It is known that this truncation can result in a significant increase in privacy loss." -> This is the introduction/background section. It sets up the problem. It feels like one long paragraph or maybe two. Let's look at the flow. It introduces DP-SGD, batching, privacy amplification, variable batch sizes, the need to hide sizes, and then the issue of truncation. I'll split it into logical paragraphs. Maybe keep the first part (background) as one paragraph, and the problems (variable sizes vs truncation) as another, or just keep it as one long paragraph if the flow is continuous. Actually, "Furthermore" starts a new thought about constraints. Let's try to break it down. * Para 1: Introduction to DP-SGD batching and privacy amplification. (Sentence 1-3) * Para 2: The problem with variable batch sizes and the truncation problem. (Sentence 4-7) * "In this work, we address both of these challenges via a simple mechanism that uses a random number of \emph{dummy points} to privatize the batch size and maintain the privacy guarantee even under truncation." -> This is the contribution/abstract summary. It could be an `

` section like "Our Approach" or just a paragraph. Since there aren't explicit section headers in the original, I should probably create semantic headers if it helps structure, or just stick to paragraphs if it's a short abstract. The prompt says "长文用

/

划分小节" (use h2/h3 for sections in long texts). This looks like an abstract. I will treat it as a single section or split into "Background" and "Contribution". * Let's look at the flow again. * Section 1: Background and Problem. * Section 2: Proposed Solution and Contributions. * Let's refine the paragraphing. * Paragraph 1: "In many practical deployments... privacy amplification results." * Paragraph 2: "Most sampling schemes... significant increase in privacy loss." (This covers the two main challenges: variable sizes and truncation). * Paragraph 3: "In this work... even under truncation." (The solution). * Paragraph 4: "We demonstrate that our mechanism... than the direct accounting for truncation recently given by (Ganesh, 2025)." (Evaluation and comparison). 2. Formatting Details: * LaTeX math: `$s$` should be preserved. HTML doesn't have a standard way to render math without external libs, but I can wrap it in `` or just leave it as `$s$` inside the text. The prompt says "代码用

", but math isn't code. I'll just leave `$s$` as is, or maybe wrap it in `` for styling if it looks like code, but usually in HTML snippets for papers, it's just text. Let's stick to text but maybe use `` for the math variable if it's distinct, or just plain text `$s$`. Let's just use plain text `$s$` as it's inline math.
    *   Emphasis: `\emph{dummy points}` -> `dummy points`.
    *   Important sentences: "The privacy guarantee... not revealed." or "It is known that this truncation... privacy loss." or the main contribution sentence. I'll use `` for the main contribution.

3.  Drafting the HTML Structure:

    *   *Section 1: Background*
        *   `
Background and Motivation
` (Wait, rule 4 says "不得增删改内容" (must not add, delete, or modify content). Adding headers like "Background and Motivation" adds content. The prompt says "长文用
/
划分小节" but also "保留原文所有信息，不得增删改内容". If I add headers, I am adding text. I should *only* use headers if the original text implies them, or maybe I should just use paragraphs and bold text to structure it? Actually, usually in these tasks, if the text is a continuous block, I shouldn't invent headers. But if it's clearly sectioned... this text looks like an abstract. I will avoid inventing headers to strictly adhere to "不得增删改内容". I will just use `
` and ``. * *Let's re-read the prompt regarding headers:* "长文用
/ 
         
划分小节". This text isn't very long (it's an abstract). So maybe just ` 
          
` is safer. * *Let's check the LaTeX:* `$s$`. I will just output `$s$`. * *Emphasis:* `\emph{dummy points}` -> `dummy points`. * *Paragraph 1:* 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. * *Paragraph 2:* 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 this limit. It is known that this truncation can result in a significant increase in privacy loss. * *Paragraph 3:* In this work, we address both of these challenges via a simple mechanism that uses a random number of dummy points to privatize the batch size and maintain the privacy guarantee even under truncation. * *Paragraph 4:* We demonstrate that our mechanism is easy to implement in a distributed setting, and provide a general analysis of this mechanism for both Poisson sampling and random allocation. Our analysis is designed to support efficient and relatively tight privacy accounting. It also effectively amplifies the privacy of the count releases by subsampling, making the expected number of dummy points asymptotically smaller than what is needed to directly privatize the (sensitivity-one) batch sizes with non-negative noise. For Poisson sampling with truncated batches, we demonstrate empirically that our mechanism achieves better privacy--efficiency tradeoffs than the direct accounting for truncation recently given by (Ganesh, 2025). 4. Refining and Adding Strong Tags: * "The privacy guarantee of these schemes requires that the batch sizes are not revealed." -> `The privacy guarantee of these schemes requires that the batch sizes are not revealed.` * "It is known that this truncation can result in a significant increase in privacy loss." -> `It is known that this truncation can result in a significant increase in privacy loss.` * "In this work, we address both of these challenges via a simple mechanism that uses a random number of dummy points to privatize the batch size and maintain the privacy guarantee even under truncation." -> `In this work, we address both of these challenges via a simple mechanism that uses a random number of <