Differentially Private Distribution Estimation Using Functional Approximation

Ye Tao, Anand D. Sarwate

Introduction

In modern data science, the Cumulative Distribution Function (CDF) serves as a foundational tool for statistical analysis. It enables researchers to derive critical metrics such as means, medians, and quantiles, and provides the basis for generating synthetic data. However, sharing a raw CDF derived from sensitive data—such as medical records or financial transactions—poses significant privacy risks.

To mitigate these risks, researchers employ Differential Privacy (DP), a framework that adds mathematical noise to data to ensure that no individual's information can be reliably identified. While several methods for private CDF estimation exist, they often struggle with a trade-off between accuracy, communication efficiency, and computational complexity. In a recent study, Ye Tao and Anand D. Sarwate from Rutgers University introduced Polynomial Projection (PP), a novel approach that leverages functional approximation to estimate distributions more effectively under strict privacy constraints.

The Limitations of Traditional Methods

Existing DP approaches for distribution estimation generally fall into two categories: Histogram Queries and Adaptive Quantiles.

  1. Histogram Queries: This method involves partitioning the data range into discrete bins and adding noise to the count of each bin. While simple, this approach often loses significant detail, especially when the number of bins is small. Conversely, increasing the number of bins requires splitting the privacy budget more thinly, leading to higher noise levels.
  2. Adaptive Quantiles: These methods iteratively search for data splits to approximate the distribution. While accurate, they are communication-heavy, requiring multiple rounds of interaction between a central server and data providers. This makes them difficult to scale in decentralized or "federated" environments where data is distributed across multiple locations.

The Polynomial Projection (PP) Approach

The core innovation of the PP method is treating the CDF as a continuous function to be approximated rather than a collection of discrete points. The process follows four primary steps:

1. Functional Approximation

Instead of counting individuals in bins, the PP method projects the empirical CDF onto a space defined by Legendre polynomials. These are a family of orthogonal functions frequently used in physics and signal processing to represent complex curves. By using these polynomials, the researchers can capture the "shape" of the distribution using only a few coefficients.

2. Moment-Based Coefficients

The coefficients of these Legendre polynomials are mathematically related to the moments of the data (such as the mean and variance). This relationship is crucial because it allows the algorithm to summarize the entire distribution through a compact set of values.

3. The Gaussian Mechanism

To satisfy the requirements of Differential Privacy, the algorithm applies the Gaussian Mechanism, adding calculated noise to the polynomial coefficients. Because the sensitivity of these moments is mathematically bounded, the researchers can precisely control the privacy-utility trade-off, ensuring that the added noise is sufficient for privacy but not so great that it destroys the utility of the data.

4. Isotonic Regression Post-processing

One side effect of adding noise to functional coefficients is that the resulting curve might "wiggle," potentially suggesting that a probability decreases as values increase—a mathematical impossibility for a CDF. To correct this, the authors apply isotonic regression, a post-processing step that ensures the final output is a valid, non-decreasing CDF.

Advantages in Decentralized and Dynamic Settings

The PP method offers significant advantages for modern, distributed data architectures:

  • Communication Efficiency: In a decentralized setting (e.g., multiple hospitals contributing to a joint study), traditional adaptive methods require constant back-and-forth communication. With PP, each site independently calculates and adds noise to its local moments. These noisy moments are then sent to a central server in a single round, where they are aggregated.
  • Simplified Updates: Managing privacy budgets when new data arrives is a common challenge in DP. With the PP method, updating a global distribution is as simple as taking a weighted average of the new noisy moments and the existing ones. This eliminates the need to re-access or re-process the original raw data.
  • Compact Representation: A private distribution can be reconstructed using as few as 5 to 7 polynomial coefficients. This makes the method exceptionally storage-efficient compared to large histograms or complex quantile trees.

Experimental Results

The researchers validated the PP method using both synthetic distributions (Normal, Lognormal, and Beta) and a real-world weight dataset containing 25,000 entries. Their findings include:

  • Superior High-Privacy Performance: In scenarios with a strict privacy parameter (e.g., $\epsilon = 0.1$), the PP method consistently outperformed Histogram Queries and remained competitive with or superior to Adaptive Quantile methods.
  • Visual Fidelity: When generating boxplots from the private estimates, the PP method captured outlier patterns and distribution tails more accurately than standard quantile-based DP methods.
  • Statistical Accuracy: Using metrics such as the Kolmogorov-Smirnov (KS) distance, Earth Mover’s distance, and Energy distance, the authors demonstrated that the PP approximation remains remarkably close to the true underlying distribution across various data shapes.

Conclusion and Future Work

Polynomial Projection represents a significant step forward in making private distribution estimation practical for real-world applications. By shifting the focus from discrete counts to functional approximation, the authors have created a method that is accurate, communication-efficient, and easy to update.

Future research will look to extend this framework to high-dimensional data, where multiple variables are tracked simultaneously. Additionally, the authors suggest exploring "dictionary learning" to identify even more efficient basis functions for representing complex, non-standard distributions. Finally, further investigation into the statistical impact of isotonic regression will help refine the utility of the post-processed outputs.

Summary updated

BibTeX
@inproceedings{tao2025differentially,
  author = {Ye Tao and Anand D. Sarwate},
  title = {{Differentially Private Distribution Estimation Using Functional Approximation}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2025},
  doi = {10.1109/icassp49660.2025.10890461},
}
Figure