Kernel Stein Method Provides Task-Aware Certificates for Rényi Differential Privacy

Rényi Differential Privacy (RDP) has become an important tool in the privacy protection field, but its computational challenges limit practical application. A recent paper proposes using Kernel Stein Discrepancies based on escort distributions to provide certificates for RDP, along with task-aware privacy guarantees. The method derives exact identities for Gaussian and Laplacian mechanisms, provides bounds for the exponential mechanism, and demonstrates through real datasets how protecting comparison sets and the release subspace jointly determine the certificate.

Computational Challenges of Rényi Differential Privacy

Rényi Differential Privacy is defined based on Rényi divergence, offering tighter privacy loss composition than pure differential privacy and is widely used in machine learning and statistical analysis. However, except for a few cases like the Gaussian mechanism, Rényi divergence typically lacks closed-form solutions, and numerical computation faces high-dimensional integration challenges. More complexly, under frameworks like Rényi Pufferfish privacy, privacy guarantees need to incorporate task-specific information, making traditional methods difficult to apply directly.

The paper's authors point out that task-aware privacy guarantees can leverage the correlation between release mechanisms and specific tasks to provide more precise privacy assessment, but computational difficulty increases accordingly. Kernel Stein Discrepancy, as a tool for measuring distribution differences, can be computed without knowing the normalization constant, offering new ideas for constructing RDP certificates.

Rényi divergence is a generalized divergence family defined on probability distributions, controlled by parameter α (α>0, α≠1). When α→1, it degenerates to KL divergence, and as α→∞, it approaches maximum divergence. RDP quantifies privacy loss by limiting the Rényi divergence of output distributions on adjacent datasets. Its core advantage lies in composition properties: composite RDP losses of multiple mechanisms can be simply added and converted to tight bounds of (ε,δ)-DP. However, for most mechanisms, Rényi divergence lacks closed-form solutions because it requires integration over the entire output space, which is infeasible in high dimensions or with complex distributions. Numerical integration methods like Monte Carlo estimation can approximate but converge slowly and lack strict reliability. Therefore, finding computable RDP upper bounds or certificates has become a key bottleneck for practical deployment.

Kernel Stein Discrepancy and Escort Distributions

Kernel Stein Discrepancy (KSD) measures the difference between two distributions through the Stein operator and functions in the Reproducing Kernel Hilbert Space (RKHS). Its advantage is that it can be computed using only samples and is insensitive to normalization constants. The paper innovatively adopts escort distributions—a type of transformed distribution obtained by reweighting the original distribution—to construct KSD. Escort distributions can highlight regions in the distribution relevant to privacy loss, making KSD more sensitive to changes in Rényi divergence.

Specifically, the authors design kernel functions based on escort distributions, making KSD a computable upper bound for Rényi divergence. By choosing different kernel functions, the tightness of the certificate can be adjusted. This construction does not depend on the specific form of the distribution, making it applicable to various privacy mechanisms.

Reproducing Kernel Hilbert Space (RKHS) is a class of function spaces with reproducing properties: for each point x, there exists a function k(x,·) such that the value of any function f at that point equals the inner product of f and k(x,·). The kernel function k is typically chosen as a Gaussian kernel or Laplacian kernel, which implicitly encodes a similarity measure between distributions. The Stein operator is constructed through the distribution's score function (i.e., the gradient of the log density), such that its expectation is zero for any test function. Kernel Stein Discrepancy combines these two: taking the norm of the Stein operator in RKHS yields a measure of difference between two distributions. Its key advantage is that it does not require knowledge of the normalization constant and can be estimated using only samples. Escort distributions are reweighted via p(x)^β / Z (β is a parameter), amplifying or reducing high-density regions of the original distribution, making KSD more sensitive to the exponential terms in Rényi divergence.

Task-Aware Privacy Certificates

Task awareness is one of the core contributions of this paper. Under the Rényi Pufferfish framework, the goal of privacy protection is to hide certain sensitive attributes, while the released data may only be relevant to specific tasks. The authors design kernel functions to focus on subspaces related to privacy directions, thereby deriving task-aware certificates. This means that if the release mechanism is insensitive to task-irrelevant directions, the privacy guarantee can be more relaxed (i.e., a tighter upper bound on privacy loss).

The paper provides exact identities for the Gaussian mechanism and Laplacian mechanism, i.e., the KSD certificate exactly equals the Rényi divergence (under specific kernels). For the exponential mechanism, an upper bound is given. These theoretical results provide actionable privacy assessment tools for practical applications.

Rényi Pufferfish privacy is the Rényi divergence version of the Pufferfish framework. Pufferfish privacy defines privacy by specifying a pair of "protecting comparison sets" (i.e., pairs of sensitive attributes that need to be distinguished) and "data generation distributions," rather than requiring uniform guarantees for all adjacent dataset pairs like differential privacy. Its advantage is the ability to incorporate task-specific information: if a sensitive attribute is irrelevant to the released data, the privacy loss can be smaller. Rényi Pufferfish applies Rényi divergence to the distribution pairs corresponding to protecting comparison sets, thereby quantifying privacy leakage for specific sensitive attributes. Task-aware certificates leverage this framework: through kernel function design, KSD is restricted to the "privacy-relevant subspace," avoiding over-penalization of irrelevant directions and obtaining tighter privacy upper bounds.

Experiments and Real Data Validation

The authors conducted experiments using a real dataset, demonstrating how protecting comparison sets (i.e., the set of sensitive attributes to be hidden) and the release subspace (i.e., the subspace of mechanism outputs) jointly determine the final certificate. Experiments show that when the overlap between the release subspace and protecting comparison sets is small, task-aware certificates can significantly reduce privacy loss estimates, validating the effectiveness of the task-aware method.

This work combines kernel methods with privacy theory, providing a computable and task-aware certificate framework for RDP. Although current results mainly target specific mechanisms, the method is expected to extend to more complex privacy models and machine learning tasks.

Key Takeaways

• Kernel Stein Discrepancy provides computable certificates for Rényi Differential Privacy, overcoming the limitations of traditional methods in handling non-Gaussian mechanisms.
• Escort distribution-based kernel design makes KSD an effective upper bound for Rényi divergence with adjustable tightness.
• Task-aware certificates provide more precise privacy guarantees under the Rényi Pufferfish framework by focusing on privacy-relevant directions.
• Certificates are exact identities under Gaussian and Laplacian mechanisms, and bounds under the exponential mechanism.
• Real data experiments show that the interaction between protecting comparison sets and release subspaces determines certificate effectiveness.

One-line Summary

Using escort distribution-based Kernel Stein Discrepancy to provide computable and task-aware privacy certificates for Rényi Differential Privacy.

Paragraph Summary

This paper addresses the computational difficulties of Rényi Differential Privacy (RDP) by proposing computable privacy certificates based on escort distribution-based Kernel Stein Discrepancy (KSD). The method constructs KSD through reweighted distributions, making it an upper bound for Rényi divergence with adjustable tightness. Under the Rényi Pufferfish framework, the authors design kernel functions focusing on privacy-relevant subspaces to achieve task-aware privacy guarantees. Theoretical analysis shows that certificates are exact identities under Gaussian and Laplacian mechanisms, and bounds under the exponential mechanism. Real data experiments validate how the interaction between protecting comparison sets and release subspaces determines certificate effectiveness, demonstrating the method's effectiveness in reducing privacy loss estimates.