Abstract
Auditing differential privacy (DP) in high-dimensional settings is a significant challenge due to the exponential sample complexity required to estimate divergences between probability distributions. This paper introduces the Regularized Kernel Rényi Divergence (RKRD), a novel framework that leverages kernel methods and quantum information theory to provide a dimension-independent auditing tool. By mapping distributions into a Reproducing Kernel Hilbert Space (RKHS) and applying a regularized quantum Rényi divergence, the authors derive an estimator with an $O(1/\sqrt{n})$ convergence rate. Experimental results on 30-dimensional synthetic data demonstrate that this approach effectively bypasses the curse of dimensionality, providing a rigorous statistical foundation for privacy auditing in complex models.
Introduction
Differential Privacy (DP) has become the standard framework for quantifying individual privacy risks in data analysis and machine learning. However, a persistent gap exists between the theoretical privacy guarantees of an algorithm and its practical implementation. Auditing—the process of empirically measuring privacy leakage by observing an algorithm's outputs—is essential to verify these guarantees.
In low-dimensional settings, auditing is relatively straightforward. However, modern machine learning involves high-dimensional outputs, such as the gradients of deep neural networks. In these spaces, traditional divergence estimators suffer from the "curse of dimensionality," where the number of samples required to accurately estimate privacy loss grows exponentially with the number of dimensions. This paper addresses this bottleneck by introducing a kernel-based approach that remains efficient regardless of the data's dimensionality.
The Kernel Rényi Differential Privacy (KRDP) Framework
The authors propose a new privacy notion termed Kernel Rényi Differential Privacy (KRDP). This framework is built upon three primary mathematical pillars:
- Kernel Mapping: Complex probability distributions are mapped into a Reproducing Kernel Hilbert Space (RKHS). In this space, distributions are represented as "covariance operators," which act as high-dimensional generalizations of covariance matrices.
- Quantum Rényi Divergence: To compare these operators, the authors adapt the Quantum Rényi Divergence from quantum mechanics. While the underlying data is classical, the mathematical structure of covariance operators in an RKHS mirrors the density operators used in quantum information theory, making this divergence a natural fit.
- Regularization: To ensure numerical stability and allow for estimation from finite samples, a regularization parameter ($\lambda$) is introduced. This leads to the Regularized Kernel Rényi Divergence (RKRD).
The RKRD Estimator
A critical contribution of this work is the development of a practical estimator for RKRD using only kernel matrices (similarity scores between samples). The authors prove that the estimation error of this tool shrinks at a rate of $O(1/\sqrt{n})$, where $n$ is the number of samples. Crucially, this rate is "parametric," meaning it is independent of the dimensionality of the output space, effectively breaking the curse of dimensionality.
Theoretical and Empirical Validation
A Hierarchy of Privacy
The paper establishes that KRDP is a "relaxation" of standard Rényi Differential Privacy (RDP). Specifically, if an algorithm satisfies $\alpha$-RDP, it is guaranteed to satisfy $(\alpha, \lambda)$-KRDP. This relationship ensures that KRDP is a valid and safe tool for auditing; any violation detected in the kernel space implies a violation in the original space.
Hypothesis Testing
Beyond point estimation, the framework supports rigorous hypothesis testing. This allows auditors to determine, with a specified statistical confidence level, whether an implementation violates its claimed privacy budget ($\epsilon$). This moves auditing from heuristic "vibe checks" to formal statistical verification.
Experimental Results
The authors validated the RKRD estimator using a synthetic Gaussian mechanism in 30 dimensions ($d=30$). While traditional auditing methods typically fail beyond a few dimensions, the RKRD estimator successfully identified privacy leaks. When the noise added to the mechanism was insufficient to meet the claimed privacy level, the RKRD curves clearly crossed the theoretical threshold, signaling a violation. Conversely, when the algorithm was correctly implemented, the estimator remained within the predicted bounds.
Discussion and Limitations
While the RKRD framework represents a significant step forward, several areas for future research remain:
- Kernel Selection: The sensitivity of the audit depends on the choice of the kernel (e.g., RBF) and its hyperparameters (e.g., bandwidth). A poorly chosen kernel may fail to capture certain types of privacy-violating patterns.
- The Regularization Gap: While the non-regularized version of the divergence satisfies the "post-processing property" (a fundamental requirement for DP), proving this property for the regularized version ($\lambda > 0$) remains an open theoretical challenge.
- Adversarial Auditing: Future work could explore "adversarial kernels"—kernels that are specifically optimized or learned to maximize the detected divergence, thereby finding the worst-case privacy leak for a given algorithm.
Conclusion
The Regularized Kernel Rényi Divergence provides a robust, computationally efficient, and dimension-independent method for auditing differential privacy. By bridging kernel methods and quantum information theory, this work provides the necessary tools to verify privacy guarantees in the high-dimensional regimes common in modern artificial intelligence.
Summary updated