Minimax Optimal Estimation of Approximate Differential Privacy on Neighboring Databases

Xiyang Liu, Sewoong OhNeurIPS 2019 · OpenReview

Differential Privacy (DP) has become the gold standard for privacy-preserving data analysis, deployed by major organizations like the U.S. Census Bureau, Google, and Apple. However, DP is notoriously difficult to implement correctly. Even if the underlying mathematics are sound, small coding bugs or floating-point errors can completely break the privacy guarantee. Furthermore, many proprietary mechanisms are "black boxes" where the public is simply asked to trust the claimed privacy parameters.

This raises a critical challenge: How do we verify the privacy of a mechanism if we can only observe its outputs?

Statistically, this is a property estimation problem. We want to estimate the "divergence" between the output distributions of two neighboring databases. Standard "plug-in" estimators (which simply look at the empirical frequency of outputs) are highly inefficient; they require a massive number of samples to provide a reliable estimate, especially when the range of possible outputs is large. This paper develops a minimax optimal estimator to verify $(\epsilon, \delta)$-Differential Privacy guarantees from black-box access, using clever polynomial approximations to achieve "sample size amplification."

Methodology: Polynomial Approximation

The authors focus on estimating the approximate DP divergence: $$d_\epsilon(P\|Q) = \sum_{i=1}^S [p_i - e^\epsilon q_i]^+$$ where $P$ and $Q$ are the output distributions of the mechanism on two neighboring databases, and $S$ is the support size.

The core difficulty in estimating this divergence is that the function $[x - e^\epsilon y]^+$ is non-smooth—it has a "kink" where the value transitions from zero. In these non-smooth regimes, standard estimators suffer from high bias.

To solve this, the authors introduce a novel estimator that:

  1. Splits the regime: It identifies "smooth" areas where a standard plug-in approach works and "non-smooth" areas where it fails.
  2. Uses Chebyshev Polynomials: In the non-smooth regime, it replaces the function with a uniformly best polynomial approximation of a carefully chosen degree ($K \approx \ln n$).
  3. Balances Bias and Variance: By using these polynomials, the estimator gracefully trades off approximation error (bias) against the noise of the samples (variance).

Key Insights: Sample Size Amplification

The "aha moment" of the paper is the mathematical proof of sample size amplification. The authors prove that their estimator, using $n$ samples, achieves the same performance that a standard plug-in estimator would achieve with $n \ln n$ samples.

Specifically, the error of their estimator scales as $\frac{e^\epsilon S}{n \ln n}$, whereas the plug-in estimator scales as $\frac{e^\epsilon S}{n}$. This logarithmic boost is a game-changer for high-dimensional output spaces. Furthermore, the authors prove this method is minimax optimal by providing a matching lower bound, showing that no other estimator can fundamentally do better in the worst-case scenario.

Experimental Results & Bug Detection

The paper evaluates the estimator using both synthetic distributions and known DP mechanisms, including Report Noisy Max (RNM), Histogram Mechanisms, and the Sparse Vector Technique (SVT)—a famous DP algorithm known for being difficult to implement correctly.

Experimental results showing MSE comparison and bug detection across various DP mechanisms.

As shown in the experimental results, the proposed estimator consistently demonstrates lower Mean Squared Error (MSE) than the plug-in method across various sample sizes. More importantly, it acts as a powerful tool for black-box accountability. In experiments, the estimator successfully detected violations in "faulty" versions of the Sparse Vector Technique (iSVT) and Histogram mechanisms. It correctly identified that these mechanisms were claiming a higher level of privacy than they actually provided, all without needing access to the underlying source code.

Limitations and Future Directions

While this framework provides a robust method for privacy auditing, it has a few limitations:

  • Finding Neighboring Databases: The paper assumes we already know which two neighboring databases ($D$ and $D'$) represent the "worst case" to test. In practice, finding these specific databases is itself a difficult search problem.
  • Continuous Outputs: The current framework is designed for discrete output spaces (size $S$). While many mechanisms can be discretized, extending this directly to continuous distributions (like pure Gaussian noise) without loss of efficiency remains an open challenge.
  • High-Dimensional Data: For mechanisms with extremely high-dimensional outputs (like a GAN generating images), the number of samples required might still be prohibitive due to the dependence on the support size $S$. Future work could involve non-parametric methods like $k$-nearest neighbors to address this scaling issue.

Summary updated

Abstract

Differential privacy has become a widely accepted notion of privacy, leading to the introduction and deployment of numerous privatization mechanisms. However, ensuring the privacy guarantee is an error-prone process, both in designing mechanisms and in implementing those mechanisms. Both types of errors will be greatly reduced, if we have a data-driven approach to verify privacy guarantees, from a black-box access to a mechanism. We pose it as a property estimation problem, and study the fundamental trade-offs involved in the accuracy in estimated privacy guarantees and the number of samples required. We introduce a novel estimator that uses polynomial approximation of a carefully chosen degree to optimally trade-off bias and variance. With n samples, we show that this estimator achieves performance of a straightforward plug-in estimator with n*log(n) samples, a phenomenon referred to as effective sample size amplification. The minimax optimality of the proposed estimator is proved by comparing it to a matching fundamental lower bound.
BibTeX
@inproceedings{liu2019minimax,
  author = {Xiyang Liu and Sewoong Oh},
  title = {{Minimax Optimal Estimation of Approximate Differential Privacy on Neighboring Databases}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=iv0tSUq9rLm},
}
Figure