📊 statistics

A Sieve-Accelerated Quadrature Method for Exact Privacy Accounting in the 2020 U.S. Decennial Census

This paper introduces a computationally efficient, sieve-accelerated quadrature method based on the discrete Fourier transform that enables the first exact, assumption-free privacy accounting for the 2020 U.S. Decennial Census, achieving a 1,824-fold speedup over prior methods while maintaining stringent numerical error tolerances.

Original authors: Buxin Su, Weijie Su, Chendi Wang

Published 2026-06-30

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Buxin Su, Weijie Su, Chendi Wang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine the U.S. Census Bureau as a giant librarian trying to share a massive, incredibly detailed book about every person in America. This book contains sensitive information like who lives where, their age, and their race. If the librarian just handed out the book as-is, bad actors could piece together the data to figure out exactly who you are and steal your identity.

To stop this, the Bureau uses a technique called Differential Privacy. Think of this as adding a tiny bit of "static" or "noise" to the book's pages before sharing them. It's like adding a few grains of sand to a bucket of water; the water still looks and acts like water, but you can't see the individual grains anymore. This protects everyone's identity.

However, there's a catch: Too much noise ruins the data. If you add too much sand, the water becomes muddy and useless for scientists trying to study population trends or for governments trying to decide how to fund schools and redraw voting districts.

The Problem: Guessing the Right Amount of Noise

For the 2020 Census, the Bureau added noise using a specific mathematical recipe (Discrete Gaussian noise). But for a long time, they couldn't calculate exactly how much privacy protection this recipe provided. They had to use a "safety margin" guess.

Think of it like a chef trying to bake a cake but being afraid of burning it. Instead of baking it for the exact 20 minutes needed, they bake it for 40 minutes just to be safe. The result? A dry, overcooked cake. Similarly, the Census Bureau was adding way more noise than necessary to be safe, making the data less useful than it could be.

They needed a way to measure the "privacy level" with extreme precision, down to a decimal point so small it's like measuring the width of a single atom. Previous methods were like trying to count every grain of sand on a beach by hand—it took too long (thousands of hours) and was practically impossible.

The Solution: A "Sieve" and a "Magic Ladder"

The authors of this paper built a new, super-fast calculator to solve this problem. They didn't just guess; they calculated the exact privacy level. Here is how they did it, using two main tricks:

1. The Magic Ladder (Trapezoidal Rule)
Imagine you need to measure the area of a wavy, bumpy hill. Usually, you'd have to take thousands of tiny measurements to get it right. The authors realized that because the math behind the Census noise has a special, repeating pattern (like a smooth, rhythmic wave), they could use a "Magic Ladder" (a mathematical tool called the trapezoidal rule).

This ladder is so efficient that instead of needing thousands of rungs to measure the hill, it only needs a few. It converges on the answer incredibly fast, giving them the precision they needed without doing millions of calculations.

2. The Sieve (The Filter)
Even with the Magic Ladder, the calculation was still too big. Imagine trying to find a few specific, glowing fireflies in a dark forest full of millions of non-glowing bugs. You don't need to look at every single bug; you only need to look where the glowing ones are.

The authors created a digital "Sieve" (inspired by an old math technique for finding prime numbers). This sieve acts like a filter that instantly identifies and throws away all the parts of the calculation that are too small to matter. It filters out the "noise" in the calculation itself, leaving only the essential parts.

The Result:
By combining the Magic Ladder and the Sieve, they turned a task that used to take 1,000 hours of computer time into one that takes less than 30 minutes.

What This Means for the Real World

Because they can now calculate the privacy level exactly, the Census Bureau doesn't have to guess anymore. They found out they were adding about 15% to 25% more noise than necessary.

By removing this excess noise, the data becomes much clearer and more useful.

For Funding: States and cities can get a more accurate picture of their population to secure the federal money they deserve.
For Politics: Redistricting (drawing voting lines) can be done with more precise data, ensuring fairer representation.
For Science: Researchers can study the economy and society with data that is both private and highly accurate.

In short, the authors built a super-fast, ultra-precise measuring tool that allows the Census to protect your privacy exactly as much as needed, without throwing away the valuable information inside the data. They turned a "dry, overcooked cake" into a perfectly baked one.

Technical Summary: A Sieve-Accelerated Quadrature Method for Exact Privacy Accounting in the 2020 U.S. Decennial Census

Problem Statement
The U.S. Census Bureau adopted differential privacy (DP) for the 2020 Decennial Census by injecting integer-valued discrete Gaussian noise into census tabulations. While the Bureau currently provides formal privacy guarantees using zero-concentrated differential privacy (zCDP), these guarantees are upper bounds on the exact privacy loss. This gap forces the injection of unnecessary excess noise to satisfy privacy budgets, degrading the statistical utility of the data for critical downstream applications like federal funding allocation and political redistricting.

The core challenge is evaluating the exact privacy profile of the 2020 Census Demographic and Housing Characteristics (DHC) File. Mathematically, this requires computing the tail probabilities of high-dimensional convolutions of heterogeneous discrete Gaussian distributions under the $f$ -differential privacy ( $f$ -DP) framework. This task is computationally prohibitive due to three factors:

Heterogeneity: Noise variances differ across queries and geographic levels, destroying the algebraic structures that allow for closed-form solutions.
Dimensionality: The composition involves up to 80-fold compositions along geographic paths, creating high-dimensional integrals.
Precision Requirements: The Census Bureau mandates exceptionally stringent numerical error tolerances (e.g., $10^{-35}$ ) to ensure the accuracy of the resulting $(\varepsilon, \delta)$ -DP curves. Prior methods required approximately 1,000 CPU hours to evaluate a single privacy budget allocation, making a full-scale accounting of the 946 distinct allocation pairs in the DHC File computationally infeasible.

Methodology
The authors propose a computationally efficient, mathematically rigorous quadrature method that reformulates the exact privacy accounting problem as a numerical integration task. The method proceeds in four key steps:

Problem Reformulation via Discrete Fourier Transform (DFT):
The problem of computing the tail probability of a weighted sum of independent discrete Gaussian random variables is transformed into a numerical integration problem. By utilizing the inverse discrete Fourier transform, the cumulative probability is expressed as an integral of the product of characteristic functions over the interval $[-\pi, \pi]$ .
Exponentially Convergent Quadrature:
The authors employ the trapezoidal rule to approximate the integral. They establish that for complex-analytic, periodic integrands (specifically the characteristic functions of discrete Gaussians), the trapezoidal rule achieves exponential convergence. This allows the required precision to be met with exponentially fewer quadrature nodes compared to standard polynomial convergence methods.
Lattice Mapping for Heterogeneous Weights:
To handle the heterogeneity of the noise parameters (where weights are rational numbers), the authors derive a unified scaling factor using Bézout's identity. This maps the heterogeneous weighted sum onto a common integer lattice, preserving the discrete probability mass function without resorting to lossy binning. This step enables the derivation of precise sub-Gaussian concentration inequalities to determine the necessary truncation bounds for the infinite sums.
Sieve-Accelerated Integration:
Despite exponential convergence, high-dimensional settings with strict tolerances ( $10^{-35}$ ) still require evaluating millions of nodes. To overcome this, the authors introduce a "sieve algorithm" inspired by number theory. This algorithm exploits the periodic peak structure of the characteristic functions to rigorously identify and prune quadrature nodes where the integrand is guaranteed to be negligible. By discarding these nodes, the method reduces the number of required function evaluations from over $10^6$ to approximately 203.

Key Contributions

Exact Privacy Accounting: The paper presents the first exact, assumption-free privacy accounting for the 2020 Census DHC File, moving beyond the upper-bound approximations of zCDP.
Computational Acceleration: The proposed method achieves a speedup of over three orders of magnitude compared to prior state-of-the-art methods. Evaluating a single privacy budget allocation drops from ~1,000 CPU hours to 0.5 CPU hours.
Scalability: The method successfully computes the exact privacy profiles for all 946 pairs of privacy budget allocations in the DHC File, a task previously deemed computationally impractical.
Theoretical Insight: The authors provide a theoretical explanation for the divergence between discrete and continuous Gaussian mechanisms using Edgeworth expansions, proving that the approximation error is of order $O(m^{-3/2})$ , where $m$ is the number of compositions.

Results

Privacy-Utility Trade-off: By using exact accounting, the authors demonstrate that the noise variance can be reduced by 15.08% to 24.82% while maintaining the same privacy guarantees as the Bureau's current zCDP-based approach. This significantly enhances the statistical utility of the released data.
Performance: The method computes the exact $f$ -DP and $(\varepsilon, \delta)$ -DP curves for the 2020 Census DHC File. The results show that the Bureau's current upper-bound approach is conservative, yielding a strictly worse privacy-utility trade-off than the exact method.
Practical Guidance: The authors observe that privacy guarantees across different composed mechanisms are highly similar. They propose using a single representative composed mechanism (specifically $[f_{M_0}, f_{M_0}]$ ) as a proxy during the privacy budget tuning phase to avoid repeated full-scale computations, with a final exact evaluation performed post-tuning.

Significance
The paper claims to solve a critical open problem posed by the Census Bureau regarding the suboptimal privacy-utility trade-off caused by loose privacy bounds. By enabling exact, assumption-free accounting, the method allows policymakers to treat privacy cost as a tunable resource, optimizing the balance between data utility and privacy protection. The framework is not limited to the Census; it offers a general, fast, and numerically reliable approach for exact privacy accounting in large-composition settings involving heterogeneous discrete mechanisms. The authors emphasize that their approach avoids the "unnecessary excess noise" that currently degrades the quality of federal data products used for redistricting and economic research.

The Problem: Guessing the Right Amount of Noise

The Solution: A "Sieve" and a "Magic Ladder"

What This Means for the Real World

More like this