arXiv CS open access

Task-aware Kernel Stein certificates for Rényi differential privacy

Leoni Carla Wirth et al. · arxiv_cs

arXiv CS · Papers

cryptography cybersecurity privacy security

Rènyi differential privacy, based on Rènyi divergence, has become a notion of choice for privacy guarantees. However, outside the Gaussian setting, Rènyi divergence can be difficult to compute. In particular, Rènyi differential privacy guarantees that exploit task-specific information, as in Rènyi P

Conceptio Open Archive

Analyze & explore related research in Conceptio

Connect this record directly into your research workflow or AI agent. Explore citations across open repositories, query full text, and export structured proof bundles.

Explore in Search →Connect via MCP / API ↗

TASK - AWARE K ERNEL S TEIN CERTIFICATES FOR R ÉNYI

arXiv:2610.23798v1 [stat.ML] 16 Oct 2026

DIFFERENTIAL PRIVACY

Leoni Carla Wirth Department of Mathematics Imperial College London London SW7 2AZ, UK l.wirth@imperial.ac.uk

Tara Trauthwein Institute for Mathematical Stochastics University of Münster Münster, Germany tara.trauthwein@uni-muenster.de

Gesine Reinert Department of Statistics University of Oxford Oxford OX1 3LB, UK gesine.reinert@stats.ox.ac.uk

A BSTRACT Rényi differential privacy, based on Rényi divergence, has become a notion of choice for privacy guarantees. However, outside the Gaussian setting, Rényi divergence can be difficult to compute. In particular, Rényi differential privacy guarantees that exploit taskspecific information, as in Rényi Pufferfish privacy, can be challenging. Here we use kernel Stein discrepancies based on escort distributions to provide certificates for Rényi differential privacy. By designing the kernel to focus on the relevant privacy directions, we also derive task-aware privacy certificates. We provide exact identities for Gaussian and Laplace mechanisms and bounds for exponential mechanisms, with separate task-aware guarantees. A real data set example illustrates how the protected comparison set and the released subspace jointly determine the resulting certificates.

Differential privacy, introduced in Dwork (2006), formalizes this by controlling how much the output distribution of a randomized mechanism can change when a single dataset entry is changed. Rényi differential privacy (RDP) (Mironov, 2017) quantifies this change using the Rényi divergence and is, for example, employed in the popular DP-SGD algorithm (Abadi et al., 2016). Standard RDP gives a privacy guarantee uniformly over all neighbouring dataset pairs. This requirement can be stronger than necessary when only certain components of the dataset are sensitive or when only particular changes of the dataset need to be protected, see for example Song et al. (2017). Several privacy notions introduce more flexible privacy specifications, for example through protected secrets or comparisons (Kifer and Machanavajjhala, 2014; He et al., 2014; Pierquin et al., 2024), individual privacy preferences (Jorgensen et al., 2015), or sensitive dataset attributes (Zhang et al., 2022).

A complementary form of privacy specification concerns the mechanism output. Divergence-based privacy notions typically compare the full output distributions of a mechanism and do not distinguish between the different directions in which these distributions may change. In some applications, however, only selected output components or distributional directions are relevant to the privacy task. For example, Gao et al. (2022) introduce subspace differ1 Introduction ential privacy, which restricts the classical notion of (ϵ, δ)differential privacy to a subspace of the output space, alPrivacy is important because there are many types of in- lowing for invariants in complementary directions to be formation that one would like to use without allowing preserved. them to circulate freely: bank records, medical data, personal information, or training data for machine learning Here, we combine these two forms of privacy specifimodels. The goal of privacy mechanisms is to make it cation using kernel Stein discrepancies. Rényi Pufferpossible to extract useful information from a dataset while fish privacy (Pierquin et al., 2024) specifies which dataset limiting what can be inferred about any single individual. comparisons require protection, while, in the sense of sub-

Task-aware Kernel Stein certificates for Rényi differential privacy

space differential privacy, the kernel is designed to capture Q relative to P by which output directions are privacy-relevant. This yields dQα|P rα privacy certificates that are task-aware. = . dP Zα (P, Q) Deriving a privacy certificate requires controlling the Details on escort distributions and standard Rényi diverRényi divergence between the corresponding output disgence can be found for example in Bercher (2012). tributions. However, outside the Gaussian setting, Rényi divergence can be difficult to compute, in particular when We say that a mechanism M is (α, ε)-Rényi differentially the distribution has an intractable normalising constant. private (RDP) if, for all neighbouring datasets D, D′ ∈ This motivates a certificate that is both computationally D, we have Dα (L(M(D)) ∥ L(M(D′ ))) ≤ ε. A comtractable and flexible enough to incorporate the privacy- prehensive overview of differential privacy notions can be relevant structure described above. We show that kernel found in Karmitsa et al. (2025). Stein discrepancies (KSDs) provide such certificates unThe Langevin KSD Throughout, we assume the relevant der suitable kernel choices. We regularity and integrability conditions and refer to Ap1. connect KSDs to Rényi divergence via escort pendix A for precise conditions. distributions and show how the kernel deterLet P be a probability measure on Rd with strictly posmines the directions captured by the discrepitive smooth density p and let Q be a probability meaancy; sure on Rd . Let K : Rd × Rd → Rd×d be a symmetric 2. derive KSD-based privacy certificate for Gauspositive semi-definite kernel, with vector-valued RKHS sian, Laplace and exponential mechanism; HK . A special case is the isotropic matrix-valued kernel 3. develop task-aware certificates combining proK(x, y) = k(x, y)Id , where Id denotes the d-dimensional tected Pufferfish comparisons with privacyidentity matrix and k(x, y) ∈ R is a scalar function; we relevant output directions then also call K a scalar kernel. The vector Langevin4. illustrate the approach on a real data set from the Stein operator is Folktables benchmark (Ding et al., 2021). TP ϕ(x) := ∇ · ϕ(x) + sP (x)⊤ ϕ(x), ϕ ∈ HK . (1) The key contribution is the construction of a discrepancy that matches the protected family of distributional The corresponding KSD is changes, together with conditions under which that disKSDK (P, Q) := sup |EQ [TP ϕ(X)]| , (2) crepancy controls privacy loss. It is not a universally bet∥ϕ∥HK ≤1 ter way to compute every Rényi divergence. The code is available at https://anonymous.4open.science/ which, if we assume that Q has strictly positive density q, and under additional assumptions detailed in Appendix A r/KSD_Renyi_DP-495A/. can also be expressed as KSDK (P, Q)2 = EX,Y ∼Q (sP (X) − sQ (X))⊤ (3) K(X, Y )(sP (Y ) − sQ (Y )) .

Preliminaries

Note that in (3) only the scores of the P and Q are required, not their normalising constants. Notation and definitions Let X be the sample space and denote by D = Dn := X n the set of all possible datasets of size n. We call D, D′ ∈ D neighbouring and write D ∼ D′ whenever they differ in only a single entry. Let M : D → Y be a randomized mechanism and PD := L(M (D)) its output distribution. Write Id for the d-dimensional identity and ⪯ for the Loewner order between positive semidefinite matrices. For a measurable map T and a probability distribution P let T# P denote the pushforward of P , so that for B measurable, T# P (B) = P (T −1 (B)). For T : Rd → Rr let JT ∈ Rr×d denote its Jacobian. For probability measures P and Q, the notation Q ≪ P states that Q is absolutely continuous with respect to P . The score function of P is sP = ∇ log p(x), when it exists.

Kernel Stein discrepancy and Rényi divergence

Here we establish a connection between Rényi divergence and kernel Stein discrepancies (KSDs) that motivates our use of KSDs as task-aware privacy certificates. Proposition B.1 shows that the first variation of the Rényi divergence can be linked to a KSD involving an escort distribution. This identity in particular shows that KSDs characterize directions of change of Rényi divergence and are thus suitable to capture the relative importance of different privacy directions.

From now on, assume that Q has a strictly positive smooth of Q induced by a For probability measures Q ≪ P and α > 1, the order- density q. We consider perturbations d d differentiable vector field ϕ : R → R . Define the pushα Rényi divergence between Q and P is Dα (Q∥P ) = 1 forward Q := (I +tϕ) Q and note that with Tt = I +tϕ α t # α−1 log Zα (P, Q), where Zα (P, Q) := EP [r ] and r = has density dQ/dP ; for a survey see Van Erven and Harremoes (2014). Furthermore, define the order-α escort Qα|P of qt (y) = q(Tt−1 (y))|det(Id + tJϕ (Tt−1 (y)))|−1 , 2

Task-aware Kernel Stein certificates for Rényi differential privacy

where Jϕ denotes the Jacobian of ϕ. Hence Qt describes by δ := mD′ − mD the displacement between the means. a perturbation of Q with Q0 = Q and initial direction ϕ. The following result is standard; see for example Table 1 Proposition 3.1. Under suitable regularity assumptions in Thierrin et al. (2022). Proposition 4.1 (Rényi divergence). The order-α Rényi (see Appendix B.1), divergence is given by Dα (Q∥P ) = α2 δ T Σ−1 δ. d sup Dα ((I + tϕ)# Q∥P ) On the other hand, let KB,A = kB (x, y)A with t=0 ∥ϕ∥HK ≤1 dt 1 T −1 = KSDK (P, Qα|P ). kB (x, y) := exp − (x − y) B (x − y) (4) 2 Proposition 3.1 provides a local characterization: the es- be an operator-valued kernel, where A ⪰ 0 and B ≻ 0. cort KSD is the maximal first variation of the Rényi di- As we assume that Σ is public, A and B are allowed to vergence over the unit ball of the RKHS. In particular, depend on Σ. the choice of the RKHS and thus of the kernel determines the perturbation directions ϕ along which changes in the With the KSD given in (2), the escort KSD can be exRényi divergence are captured. In Section 5, this obser- pressed as follows. vation will allow us to adapt the KSD to privacy-relevant Proposition 4.2 (Escort KSD). Under appropriate condirections. ditions (see Appendix A), the KSD based on the kerMoreover, for α = 1, the escort distribution is Q and nel K = KB,A satisfies Proposition 3.1 illustrates a connection between KSD and KSDKB,A (P, Qα|P )2 = cB,Σ α2 (Σ−1 δ)⊤ AΣ−1 δ, the first variation of Kullback–Leibler divergence under −1/2 smooth transport; see Liu and Wang (2016). where cB,Σ := E[kB (X, Y )] = { det(I + 2ΣB −1 )} . Remark 3.2. Under suitable assumptions, the local representation in Proposition 3.1 can be extended to a global Thus, for the kernel K = KB,A the comparison between representation of the Rényi divergence along a particular KSD and Rényi divergence given in Proposition 4.1 reflow, see Remark B.5 for an example. However, an eval- duces to comparing the variance Σ and A. uation would require to access the KSD along the entire A specific kernel choice. We now consider the flow. Our privacy certificates in Section 4 instead seek anisotropic kernel KB,A obtained by setting A = Σ to to control Rényi divergence from the KSD evaluated at a match the covariance structure of the privacy mechanism, single distribution pair. i.e. KB,Σ (x, y) := kB (x, y)Σ. We refer to the Appendix B.2 for the isotropic choice A = Id .

KSD as privacy certificate

4.1

The Gaussian mechanism

The following theorem shows that this covariancematched kernel allows to derive an equality (up to conWe now view the local connection between Rényi diver- stants) of both quantities gence and the KSD derived in Proposition B.1 in the Theorem 4.3. For the kernel K = K B,Σ we obtain, framework of differential privacy by considering P = PD ′ 1 and Q = PD′ for neighbouring D ∼ D . Then, any Dα (Q∥P ) = KSDKB,Σ (P, Qα|P )2 . bound Dα (PD′ ∥PD ) ≤ ϵ obtained uniformly over D ∼ 2αcB,Σ D′ yields an (α, ϵ)-RDP guarantee. We identify kernel 2 choices under which the KSD tightly controls the corre- Thus, if KSDK (P, Qα|P ) ≤ ϵ uniformly over all neigh′ sponding Rényi divergence. Some numerical illustrations bourhoods D ∼ D then the Gaussian mechanism satisϵ supporting these theoretical results are given in Appendix fies (α, 2αcB,Σ )-RDP. C. Remark 4.4 (Kernel choice). The covariance-matched kernel KB,Σ (x, y) = kB (x, y)Σ aligns the KSD with Rényi divergence, yielding the equality in Theorem 4.3. In contrast, the isotropic kernel KB,Id (x, y) = kB (x, y)Id weights directions δ by Σ−2 rather than Σ−1 , and can give a substantially looser certificate; see Appendix B.2. Thus, even in this simple Gaussian setting, a suitable kernel choice is essential for obtaining a tight privacy certificate.

For the Gaussian location family, one can compare the KSD and Rényi divergence directly. Since both quantities are explicitly computable, this provides a tractable setting in which to compare the influence of the operator-valued kernel choice in KSD. All proofs of this subsection can be found in Appendix B.2. Let mD ∈ Rd be the parameter associated to a dataset D ∈ D. The output distribution of the Gaussian mechanism is given by PD = N (mD , Σ), where Σ ≻ 0 is assumed to be public. For a fixed neighbouring pair (D, D′ ) we write P := PD and Q := PD′ , and denote

4.2

The Laplace mechanism

The previous subsection showed that adapting the operator-valued kernel to the privacy mechanism can improve the tightness of the bounds. We now focus on the 3

Task-aware Kernel Stein certificates for Rényi differential privacy

Remark 4.8 (Kernel choice). The corresponding RKHS consists of constant vector fields and thus k0 is not characteristic on a general class of probability measures. However, as Theorem 4.7 shows, it is sufficient here because the P and Q differ only in the location parameter; see (5). The constant kernel gives an explicit inverse, whereas the RBF kernel requires numerical inversion. For more details see Appendix B.3.

underlying scalar kernel and show that its choice can determine whether the KSD provides a useful global bound. To isolate this effect, we study the Laplace mechanism in one dimension, so that the relevant choice is the underlying scalar kernel. The proofs of this subsection can be found in Appendix B.3. Let mD ∈ R be the parameter associated to a dataset D ∈ D. The output distribution of the Laplace mechanism is given by PD = Lap(mD , b) with 1 |x − mD | pD (x) = exp − , (5) 2b b

4.3

The exponential mechanism

Section 4.1 and Section 4.2 showed that the escort KSD can certify Rényi differential privacy of the Gaussian and where b > 0. For a fixed neighbouring pair (D, D′ ) we Laplace mechanism, respectively. We now study this corwrite P := PD and Q := PD′ and denote the correspond- respondence for the exponential mechanism with a focus ing densities by p = pD and q = pD′ , respectively. Fur- on regular natural exponential families. In contrast to the thermore, we again set δ := mD′ − mD to be the dis- Gaussian and Laplace mechanisms, the Rényi divergence placement between the means. may involve intractable normalizing constants, whereas The Rényi divergence is available in closed form; see Gil the score differences entering the KSD do not. Thus, the derived certificate will not only allow us to incorporate reet al. (2013); Mironov (2017). For α > 1, define stricted privacy assumptions efficiently, but also improve (α−1)u αe + (α − 1)e−αu 1 , u > 0. the computability. Rα (u) := log α−1 2α − 1 Let (Pη )η∈H be the regular natural exponential family Proposition 4.5 (Rényi divergence). For P Pη (dy) = pη (y) ν(dy) = exp(η ⊤ T (y) − A(η))ν(dy) and Q the Laplace output distributions of a (7) neighbouring dataset pair (D, D′ ), we obtain with differentiable sufficient statistic T : Rd → Rr and Dα (Q∥P ) = Dα (P ∥Q) = Rα |δ| b . base measure ν(dy) = h0 (y) dy for h0 (y) > 0 smooth. On the other hand, let k : R × R → R be a positive Moreover, A is the log-partition function defined by Z semidefinite scalar kernel. Using (3), the escort KSD can be expressed as follows. A(η) := log exp η ⊤ T (y) ν(dy). (8) Proposition 4.6 (Escort KSD). Under the conditions detailed in Appendix A, the KSD based on the scalar ker- We assume that every A(η) appearing below is finite. Furthermore, we assume that the exponential family is nel k satisfies minimal, so that the Fisher information matrix I(η) = KSDK (P, Qα|P )2 ∇2 A(η) is positive definite for every η ∈ H. 2 4α Suppose that the data dependence enters through the nat= 2 EX,Y ∼Qα|P k(X, Y )1{X∈Iδ } 1{Y ∈Iδ } , b ural parameter η = ηD and assume that the base denwhere X and Y are independent and Iδ := sity h0 is independent of the dataset. For neighbouring dataset pairs (D, D′ ) with corresponding natural param(min{mD , mD + δ}, max{mD , mD + δ}). eters η = ηD and ηD′ , we write P = Pη , Q = Pη+δ , Proposition 4.6 shows that the discrepancy is supported δ := ηD′ − ηD , and ηt = η + tδ, t ∈ [0, α]. Furtheronly on the interval between the two modes. Thus, the more, we assume that ηt ∈ H for every t ∈ [0, α]. Given global behavior of the KSD is determined by how the un- a dataset D, the exponential mechanism returns a random derlying kernel k accounts for this localized discrepancy. output Y ∼ PηD . A detailed introduction to the expoWe study the constant kernel k(x, y) := k0 (x, y) := 1 nential mechanism in this setting as well as all proofs are and refer to Appendix B.3 for a study of the Gaussian RBF given in Appendix B.4. kernel. For every α > 1 for which A(ηα ) < ∞, Theorem 4.7. For k0 (x, y) ≡ 1, A(ηα ) − αA(η1 ) + (α − 1)A(η0 ) |δ| |δ| Dα (Q∥P ) = ; (9) α e(α−1) b − e−α b α−1 KSDk0 (P, Qα|P ) = . |δ| b αe(α−1) |δ| see for example (15) in Thierrin et al. (2022). Here we b + (α − 1)e−α b give an alternative expression for the Rényi divergence. Set κα := b KSDk0 (P, Qα|P ) ∈ [0, 1). Then Proposition 4.9 (Rényi divergence). Let P = Pη be a member of the natural exponential family defined above. 1 α−1 log 1−κα α log 1 + α κα Then for every α > 1 for which A(ηα ) < ∞, Dα (Q∥P ) = − . 2α − 1 (α − 1)(2α − 1) α ¯ α Dα (Q∥P ) = δ ⊤ I((η (10) t )t=0 )δ (6) 2 4

Task-aware Kernel Stein certificates for Rényi differential privacy

R Rα ¯ t )α ) := 2 1 tI(ηt )dt+ 2 Theorem 4.13. Under Assumptions 4.11 and 4.12 we with I((η t=0 α 0 α(α−1) 1 (α − t)I(ηt )dt. have Although (9) looks explicit, its ingredients may not be CH easy to compute as it requires evaluating the (possibly inKSDK (P, Qα|P )2 . (11) Dα (Q||P ) ≤ 2α κ H tractable) log-partition function A. In contrast, the KSD is built up on score functions which can be evaluated with- Thus, if KSD (P, Q )2 ≤ ϵ uniformly over all neighK α|P out knowledge of the normalization constants; the compu- bourhoods D ∼ D′ then the exponential mechanism sattational burden depends on escort sampling and on estab- isfies (α, CH ϵ)-RDP. 2α κH lishing the comparison constants. To make this precise, we now derive an explicit expression of the KSD certifi- Remark 4.14. Within the class of natural regular exponential families we cannot hope for a general escort KSD cate. bound of the Rényi divergence. For example for the expod d d×d Let K : R × R → R be an operator-valued kernel nential family p (x) = −ηeηx , for x ≥ 0 and η < 0, we η such that the matrix have for all ηD′ = η + δ < 0, so that by (9), T r×r GK (ηt ) := EX,Y ∼Pηt JT (X)K(X, Y )JT (Y ) ∈ R h (−η − δ)α (−η)1−α i 1 is well-defined. Then the escort KSD obtains the followDα (Q||P ) = , log α−1 −αδ − η ing explicit expression. Proposition 4.10. (Escort KSD) Let P = Pη be a mem- which is finite only when η + αδ < 0. In particular, ber of the natural exponential family (7). Under the con- the escort density cannot be normalized. Our assumptions ditions laid out in Appendix A, provide sufficient conditions for a certificate, but are not claimed to be necessary. KSDK (P, Qα|P )2 = α2 δ T GK (ηα )δ. We conclude this section with three applications for which Assumptions 4.11 and 4.12 are satisfied. Corollary 4.15 (Laplace family). Let Pη = Lap(0, −η −1 ), η ∈ H ⊂ R<0 , be the centered Laplace family, written in natural form as For every η ∈ H define ∆η = {ηD′ − ηD : D ∼ pη (x) = exp(η |x| − A(η)) with sufficient statisD′ and ηD = η} ⊂ Rr to be the set of attainable neigh- tic T (x) = |x| and Lebesgue base measure. Assume bouring directions at η. To relate the Fisher information that H is chosen such that ηmin ≤ ηt ≤ ηmax < 0 for and the kernelized metric uniformly over neighbouring all t ∈ [0, α] and let K(x, y) = k(x, y) = xy. Then KSDK (P, Qα|P )2 ≤ ϵ uniformly over all D ∼ D′ datasets, we make the following two assumptions. 2 Assumption 4.11 (Poincare inequality on H). Assume implies (α, ηmin ϵ)-RDP. 2 2αηmax that there exist a constant 0 < CH < ∞ such that, for Corollary 4.16 (Gaussian family). Let P = Pη belong every η ∈ H, δ ∈ ∆η and t ∈ [0, α], to the Gaussian natural exponential family with sufficient 2 VarPηt δ ⊤ T (X) ≤ CH EPηt JT (X)⊤ δ . statistic T (x) = x, base measure ν = N (a, Σ), a ∈ Rd and Σ ≻ 0. Set K(x, y) = ψ(∥x − y∥)Id for some For the regular natural exponential family, δ ⊤ I(η)δ = ψ : R → R+ . Then, for κH = EZ∼N (0,2Σ) [ψ(∥Z∥)] VarPη δ ⊤ T (X) , see (Wainwright and Jordan, 2008, and λmax (Σ) the largest eigenvalue of Σ, a bound Corollary 3.1). Thus, Assumption 4.11 relates the Fisher KSDK (P, Qα|P )2 ≤ ϵ uniformly over all D ∼ D′ iminformation to the squared gradient of the sufficient statisλmax (Σ) tic T , while the next assumption relates this gradient to the plies (α, 2α κH ϵ)-RDP. A comparison of Proposition 4.9 and 4.10 reveals the same role of the kernel as in the previous two subsections. More precisely, controlling Rényi divergence by the escort KSD reduces to comparing the Fisher information I(η) and the kernelized metric GK (ηα ).

kernelized matrix GK . Assumption 4.12. Assume that there exists a constant κH > 0 such that, for every η ∈ H and δ ∈ ∆η , 1 ⊤ ¯ t )α J((η δ GK (ηα )δ, t=0 ) ≤ κH n R 2 2 1 ⊤ ¯ t )α ) := where J((η dt + t=0 α 0 tEPηt JT (X) δ o Rα 2 2 ⊤ dt . α(α−1) 1 (α − t)EPηt JT (X) δ

Corollary 4.17 (Quartic family). Let P = Pη belong to the natural exponential family with sufficient statistic T (x) = x and base density h0 (x) ∝ Pd 1 ⊤ exp − 2 x Σx − γ4 i=1 x4i , for some Σ ≻ 0 and γ > 0. Consider the constant kernel K(x, y) = Id and let λmin (Σ) be the smallest eigenvalue of Σ. Then KSDK (P, Qα|P )2 ≤ ϵ uniformly over all D ∼ D′ imϵ plies (α, 2αλmin (Σ) )-RDP.

Assumption 4.12 excludes kernels that are insensitive to a protected change and quantifies how strongly the end- 5 Task-aware KSD certificates for Rényi Pufferfish privacy point discrepancy detects that change relative to its variation along the interpolation path. Under these assumptions, we finally derive an escort KSD certificate for the In Section 4 we showed how escort KSDs can be used Rényi divergence. to derive certificates for RDP, and that the kernel choice 5

Task-aware Kernel Stein certificates for Rényi differential privacy

determines which changes in the output distribution are captured by the certificate. We now build on this observation by constructing kernels that target specified privacy tasks, leading to task-aware Rényi privacy certificates.

Task-aware RPP is in general strictly weaker than full RPP: it protects only the task-aware output US⊤ M (D) and places no privacy constraint on changes in S⊥ . In particular, full RPP implies task-aware RPP.

5.1

5.3

Rényi Pufferfish privacy

Task-aware kernel design

A Pufferfish framework (Kifer and Machanavajjhala, 2014) is a triple (S, Q, Θ), where S is a collection of secrets, Q ⊆ S × S is the collection of protected secret pairs, while Θ indexes a class of data-generating distributions Pθ and represents admissible adversarial prior knowledge. For any θ ∈ Θ, let Pθ denote a dataset distribution on D and let D ∼ Pθ . In particular, the dataset D is now random. We remark that the protected secret pairs in Q are ordered because Rényi divergence is asymmetric.

We now illustrate how the underlying kernel can be used to obtain task-aware privacy guarantees. We first return to the Gaussian setting of Subsection 4.1, now for the secret-conditioned output laws. Assume that Pθ,s = N (mθ,s , Σ), where mθ,s ∈ Rd depends on the secret s ∈ S and θ ∈ Θ, while the covariance Σ ≻ 0 does not change across secrets. For a fixed protected pair (si , sj ) ∈ Q and a θ ∈ Θ, we write P := Pθ,si and Q := Pθ,sj , and denote by δ = mθ,sj − mθ,si the displacements between the means. The order-α escort of Q For a secret s ∈ S with Pθ (s) > 0, define the output law relative to P is Qα|P = N (mθ,si + αδ, Σ), see B.2. Pθ,s := L M (D) | s, θ , where D ∼ Pθ . As in Subsection 4.1 we study the anisotropic kernel := kB (x, y)A for some B ≻ 0. We focus Definition 5.1 (Rényi Pufferfish privacy, Pierquin et al. KB,A (x, y) d on A = A = (ΣUS )(US⊤ ΣU )−1 (ΣUS )⊤ ∈ Rd×d . (2024)). Let α > 1 and ε ≥ 0. A mechanism M S is (α, ε)-Rényi Pufferfish private (RPP) in (S, Q, Θ) if Theorem 5.3. Let S be a public task subspace with or Dα Pθ,sj Pθ,si ≤ ε for every θ ∈ Θ and every thonormal basis US ∈ Rd×r and kernel KB,Ad . Then S (si , sj ) ∈ Q such that Pθ (si ) > 0 and Pθ (sj ) > 0. 1 Dα ((US⊤ )# Q∥(US⊤ )# P ) = KSDKB,Ad (P, Qα|P )2 . 2αcB,Σ S We refer to Appendix B.5 for a more detailed introduction to Rényi Pufferfish privacy and a collection of its properIf furthermore Σ−1 δ ∈ S, then ties. 1 Dα (Q∥P ) = KSDKB,Ad (P, Qα|P )2 . 5.2 Task-aware Rényi Pufferfish privacy 2αcB,Σ S Remark 5.4 (Task awareness). By projecting P and Q onto S, we protect only the output directions and thus obtain only task-aware RPP. However, if all privacy-relevant changes lie in S, i.e. if Σ−1 δ ∈ S, then task-aware and full RPP align and KSD certifies full RPP. Remark 5.5 (Kernel choice). The kernel choice is again essential. Here, we require a kernel that retains the output directions specified by the task subspace while disregarding directions that are intentionally excluded by the task. This illustrates the power of KSD: through the choice of kernel, one can specify which distributional directions the certificate measures and, thus, which privacy-relevant changes it is designed to detect. We note that such a kerLet S ⊆ Y = Rd be a public task subspace that is fixed nel should be built on a public, justified task specification, independently of the datasets and set r = dim(S). The rather than chosen post hoc to suppress privacy-relevant subspace specifies the components of the mechanism outdirections. d×r put that are relevant for the required task. Let US ∈ R be the orthonormal basis of S. We define the task-aware mechanism by mapping the output M (D) of the original 5.4 Task-aware certificates for the exponential family mechanism to its coordinates in the task subspace S, i.e. ⊤ by US M (D). Finally, we derive task-aware certificates for the expoDefinition 5.2 (Task-projected Rényi Pufferfish private). nential mechanism. As in Subsection 4.3, we focus on Let α > 1 and ε ≥ 0. We call a mecha- regular natural exponential families and thus assume that nism M (α, ϵ)-task-aware Rényi Pufferfish private with the secret-conditioned output laws Pθ,s are part of one of task subspace S and Pufferfish framework (S, Q, Θ) if these families, where the dependence on the secret s ∈ S Dα (US⊤ )# Pθ,sj (US⊤ )# Pθ,si ≤ ε for every θ ∈ Θ and and on the prior θ ∈ Θ enters through the natural paramevery (si , sj ) ∈ Q such that Pθ (si ) > 0 and Pθ (sj ) > 0. eter η = ηθ,s . Then, for a pair of secrets (si , sj ) ∈ Q Subsection 5.1 introduces RPP, which we will also refer to as full RPP, as it controls the Rényi divergence between the full outputs Pθ,sj and Pθ,si . We now introduce a weaker, task-specific guarantee by additionally restricting the output directions that are protected. Following the idea of subspace differential privacy (Gao et al., 2022), we restrict the privacy guarantee to a specified output subspace, but in contrast to Gao et al. (2022) we combine this restriction with Rényi Pufferfish privacy instead of (ϵ, δ)differential privacy. This yields a task-aware privacy guarantee that restricts both the protected secret comparisons and the protected output directions.

Task-aware Kernel Stein certificates for Rényi differential privacy

we set η = ηθ,si and write P = Pη , Q = Pη+δ , δ := ηθ,sj − ηθ,si , as well as ηt = η + tδ. We assume that ηt ∈ H for every t ∈ [0, α]. Finally, for every η ∈ H we set ∆Q η = {ηθ,sj −ηθ,si : θ ∈ Θ, (si , sj ) ∈ Q and ηθ,si = η} ⊂ Rr to be the set of protected secret-comparison directions at η. Note that the pairs of secrets are ordered as Rényi divergence is asymmetric. If both orientations are intended, both (si , sj ) and (sj , si ) should be included in Q or verified separately.

Appendix C.3. Hence the constant kernel misses the protected distributional change, while the feature kernel in Corollary 5.8 detects it. Example 5.10. Take d = 40, α ∈ {1, 2, 4, 8}, γ = 0.1, δ = 0.1094, and Σ and a are generated such that δa⊤ Σ−1 a = 0.05. Details can be found in Appendix C.3. While the KSD can be calculated in closed form, the escort moment mα still has to be estimated numerically; we use MCMC for this task. The results are shown in Table 1. The estimated KSD certificates are of the same order The specified Pufferfish restrictions allow to relax Asof magnitude as the approximated Rényi divergence, but sumptions 4.11 and 4.12 by specifying the set of attainable are faster to compute. Thus, if runtime is an issue, KSD Q neighbouring directions from ∆η to ∆η , see Assumpmay be preferred. tions 4.11a and 4.12a in Appendix B.7.

We now consider a special kernel KS that restricts the KSD to the task subspace S. Under the assumptions above, this task-aware kernel can nevertheless provide a certificate for full RPP. Proposition 5.6. Let S be a public task subspace with projector US and define KS (x, y) := k(x, y)US US⊤ to be a task-aware kernel with scalar kernel k. Assume that Assumptions 4.11a and 4.12a are satisfied with K = KS . Then CH Dα (Q∥P ) ≤ KSDKS (P, Qα|P )2 . 2α κH A uniform bound on KSDKS for all θ ∈ Θ and (si , sj ) ∈ Q implies the corresponding RPP guarantee. Remark 5.7. We remark that the Pufferfish (∆Q η ) restriction and the subspace restriction (K = KS ) are complementary: ∆Q η specifies which secret comparisons require protection, which makes Assumptions 4.11a and 4.12a easier to verify than Assumptions 4.11 and 4.12, while S specifies the privacy-relevant output directions. If JT (x)⊤ δ ∈ S for all δ ∈ ∆Q η , then Assumption 4.12 with kernel K(x, y) = kB (x, y)Id implies Assumption 4.12a with kernel K = KS . Corollary 5.8. Let P = Pθ,s belong to the natural exponential family with sufficient statistic T (x) = 1 ⊤ 2 ∈ R, x ∈ Rd and a ∈ Rd such that 2 (a x) ∥a∥ = 1, and base density h0 (x) as in Corollary 4.17. Let S = span(a) be the public task subspace. Assume that ∆Q η ⊂ R+ for all η ∈ H, and that ηmax := supη∈H, δ∈∆Q (η + αδ) < (a⊤ Σ−1 a)−1 . Also η assume that κH =

inf

η∈H;δ∈∆Q η

ACSIncome illustration

We use the ACSIncome data from the Folktables benchmark (Ding et al., 2021) to give a real-data illustration of the output-side task restriction developed above. The ACSIncome data is a popular benchmark; see for example Bullwinkel et al. (2022). The classical task is to predict y, indicating whether an individual’s annual income exceeds $50,000, using demographic and employment variables such as age, education, occupation, marital status, hours worked, sex, and race. We are given a sample of 20,000 records from California, and 20,000 records from Texas. In this experiment the 2018 California records form public auxiliary data; the 2018 Texas records are the pseudoprivate data. We fit a public logistic regression model with ridge penalty to the public data release. For the full data release we use a Gaussian mechanism with a vector release, and for the task-aware mechanism we use the same Gaussian variables but release only its scalar projection. Details are found in Appendix D. Figure 1 gives the standard RDP and the task-aware RDP, plotted against privacy budget; the dashed lines indicate empirical 95% quantiles serving as diagnostics. The taskaware RDP certificate uses a smaller privacy budget than the standard release, for a different release mechanism. In Appendix D we also consider a Pufferfish example, keeping sex and race indicators secret for a particular individual. Figure 6 shows that restricting the released output can change the relative importance of different protected comparisons.

EX∼Pη+αδ [(a⊤ X)2 ] > 0.

Take k(x, y) = (a⊤ x)(a⊤ y), so that KS (x, y) = (a⊤ x)(a⊤ y)aa⊤ . Then, if KSDKS (P, Qα|P )2 ≤ ϵ uniformly over all θ ∈ Θ and (si , sj ) ∈ Q, we obtain ϵCH ⊤ ⊤ −1 (α, 2α a. κH )-RPP, where CH = a (Σ − aηmax a )

Conclusion

We used kernel Stein discrepancies to derive tractable certificates for Rényi differential privacy that can incorporate privacy specifications. The kernel plays a central role in these certificates by determining which directions of change are captured. This flexibility leads to taskaware certificates that combine restrictions on the protected comparisons with restrictions on the relevant output directions. Our theoretical examples and the ACSIncome illustration demonstrate the resulting framework in concrete settings. While the KSD computations

Remark 5.9. With the kernel KS of Corollary 5.8, and mα = EPη+αδ [(a⊤ X)2 ], Proposition 4.10 gives that KSDKS (P, Qα|P )2 = α2 δ 2 m2α . If instead we chose the constant scalar kernel giving KS = aa⊤ then by symmetry, KSDKS (P, Qα|P )2 = α2 δ 2 EQα|P [(a⊤ X)]2 = 0, see 7

Task-aware Kernel Stein certificates for Rényi differential privacy

α 1 (KL) 2 4 8

bα D 5.588e − 04 sd 2.98e−05 1.137e − 03 sd 5.12e−05 2.463e − 03 sd 6.60e−05 5.621e − 03 sd 1.23e − 04

est. KSD bound (37) 1.300e − 03 sd 4.69e−05 2.868e − 03 sd 1.03e−05 7.171e − 03 sd 2.65e − 04 2.389e − 02 sd 9.35e − 04

bα bound / D 2.327

fallback (38) 1.385e − 03

tD (s) 1.75

tKSD (s) 0.57

CH 0.4810

2.521

3.086e − 03

2.83

0.56

0.5078

2.911

7.812e − 03

5.21

0.58

0.5713

4.25

2.778e − 02

9.79

0.56

0.7614

Table 1: Dense-quartic order study; 50 independent MCMC repetitions. The order α = 1 row is the KL limit. The KSD bound is the estimated normalized task-aware privacy certificate (37) (with the MCMC estimate for the escort moment). The fallback option is the cruder bound (38). The tD and tKSD columns show the runtimes. writing of proofs, design experiments and provide feedback on research methodology and experiments, implement methods, and interpret results. We have not used generative AI tools to generate synthetic data sets, assist with translation, clean and reformat dataset, support qualitative and thematic data analysis. Additionally, we used generative AI tools to create software code, draft parts of a research paper, identify relevant literature, suggest edits to the paper to improve readability, to summarize existing literature and identify gaps, for brainstorming, sourcing/searching for information, and to suggest experimental parameters. We have reviewed all AI-assisted work. More precisely, we checked all LLM-generated research ideas for potential plagiarism and for overlap with existing work through a manual literature survey. Furthermore, we checked all LLM-assisted claims and proofs line by line by independently working out the resulting arguments, checking every step for correctness, and supplying all necessary details, justifications, and assumptions. The LLM-generated code was verified and tested for correctness by one author. We independently evaluated all LLMsuggested methodological approaches and experimental designs for their validity and suitability. Additionally, all LLM-assisted interpretations and conclusions were independently assessed against the underlying results. All sources and citations were independently verified. The final research decisions remain with the authors.

Figure 1: The full Gaussian release and its onedimensional task-aware release using the same Gaussian noise. Solid curves show the analytic certificates, and dashed curves show the empirical 95th percentiles over sampled replace-one Texas training pairs. are not necessarily fast, in future work we shall explore how Nyström approximations can reduce the large-sample computational cost for KSD computation; see Kalinke et al. (2024).

Privacy mechanisms should be evaluated also regarding their utility. We leave a study of connections with utility measures as future work; the choice of privacy kernel for We take responsibility for the final content of this work, certification could depend on the downstream task. Kernel including text, claims, or artifacts produced with the aid choice in itself is a direction for future research, as is the of generative AI. treatment of other privacy notions in the KSD framework. References Lastly we note that privacy can be in tension with other desirable criteria such as fairness; see for example Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Fioretto et al. (2022). Depending on the criteria, output Deep learning with differential privacy. In Proceedings of private mechanisms may create undesirable side-effects of the 2016 ACM SIGSAC Conference on Computer and which have to be acknowledged separately. Communications Security, pages 308–318, 2016. Jordan Awan, Ana Kenney, Matthew Reimherr, and Aleksandra Slavković. Benefits and pitfalls of the exponential mechanism with applications to Hilbert spaces and functional PCA. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 374–384. PMLR, 2019.

AI use statement In this work, we used generative AI tools to help develop the conceptual framework of escort distributions, formulate mathematical claims relating to connections between RDP and KSD, provide critical ingredients for proving mathematical claims in Proposition A.1 , assist in the 8

Task-aware Kernel Stein certificates for Rényi differential privacy

In 2015 IEEE 31St International Conference on Data Dominique Bakry, Ivan Gentil, and Michel Ledoux. AnalEngineering, pages 1023–1034. IEEE, 2015. ysis and Geometry of Markov Diffusion Operators, volume 348 of Grundlehren der mathematischen Wis- Florian Kalinke, Zoltán Szabó, and Bharath K Sripesenschaften. Springer, 2014. rumbudur. Nyström kernel Stein discrepancy. arXiv Alessandro Barp, Francois-Xavier Briol, Andrew Dunpreprint arXiv:2406.08401, 2024. can, Mark Girolami, and Lester Mackey. Mini- Napsu Karmitsa, Antti Airola, Tapio Pahikkala, and Tinja mum stein discrepancy estimators. In H. Wallach, Pitkämäki. A comprehensive guide to differential priH. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, vacy: From theory to user expectations. arXiv preprint and R. Garnett, editors, Advances in Neural InforarXiv:2509.03294, 2025. mation Processing Systems, volume 32. Curran AssoDaniel Kifer and Ashwin Machanavajjhala. Pufferfish: A ciates, Inc., 2019. framework for mathematical privacy definitions. ACM J-F Bercher. A simple probabilistic construction yielding Transactions on Database Systems (TODS), 39(1):1– generalized entropies and divergences, escort distribu36, 2014. tions and q-Gaussians. Physica A: Statistical MechanQiang Liu and Dilin Wang. Stein variational gradient deics and its Applications, 391(19):4460–4469, 2012. scent: A general purpose Bayesian inference algorithm. Blake Bullwinkel, Kristen Grabarz, Lily Ke, Scarlett In Advances in Neural Information Processing Systems Gong, Chris Tanner, and Joshua Allen. Evaluating the 29, 2016. fairness impact of differentially private synthetic data. Qiang Liu, Jason Lee, and Michael Jordan. A kernelarXiv preprint arXiv:2205.04321, 2022. ized Stein discrepancy for goodness-of-fit tests. In Kacper Chwialkowski, Heiko Strathmann, and Arthur Maria Florina Balcan and Kilian Q. Weinberger, edGretton. A kernel test of goodness of fit. In Maria Floitors, Proceedings of The 33rd International Conferrina Balcan and Kilian Q. Weinberger, editors, Proence on Machine Learning, volume 48 of Proceedings ceedings of The 33rd International Conference on Maof Machine Learning Research, pages 276–284, New chine Learning, volume 48 of Proceedings of Machine York, New York, USA, 20–22 Jun 2016. PMLR. Learning Research, pages 2606–2615, New York, New Ilya Mironov. Rényi differential privacy. In 2017 York, USA, 20–22 Jun 2016. PMLR. IEEE 30th Computer Security Foundations Symposium Frances Ding, Moritz Hardt, John Miller, and Ludwig (CSF), pages 263–275. IEEE, 2017. Schmidt. Retiring adult: New datasets for fair machine learning. Advances in neural information processing Clément Pierquin, Aurélien Bellet, Marc Tommasi, and Matthieu Boussard. Rényi pufferfish privacy: General systems, 34:6478–6490, 2021. additive noise mechanisms and privacy amplification Cynthia Dwork. Differential privacy. In International colby iteration via shift reduction lemmas. In Forty-first loquium on automata, languages, and programming, International Conference on Machine Learning, 2024. pages 1–12. Springer, 2006. John Pike and Haining Ren. Stein’s method and the Ferdinando Fioretto, Cuong Tran, Pascal Van Hentenryck, Laplace distribution. ALEA, 11:571–587, 2014. and Keyu Zhu. Differential privacy and fairness in deShuang Song, Yizhen Wang, and Kamalika Chaudhuri. cisions and learning tasks: A survey. arXiv preprint Pufferfish privacy mechanisms for correlated data. In arXiv:2202.08187, 2022. Proceedings of the 2017 ACM International ConferJie Gao, Ruobin Gong, and Fang-Yi Yu. Subspace difference on Management of Data, pages 1291–1306, 2017. ential privacy. In Proceedings of the AAAI Conference Ingo Steinwart and Andreas Christmann. Support Vector on Artificial Intelligence, volume 36, pages 3986–3995, Machines. Springer, New York, 2008. doi: 10.1007/ 2022. 978-0-387-77242-4. Manuel Gil, Fady Alajaji, and Tamas Linder. Rényi divergence measures for commonly used univariate continu- Ferenc Cole Thierrin, Fady Alajaji, and Tamás Linder. Rényi cross-entropy measures for common distribuous distributions. Information Sciences, 249:124–131, tions and processes with memory. Entropy, 24(10): 2013. 1417, 2022. Xi He, Ashwin Machanavajjhala, and Bolin Ding. Blowfish privacy: Tuning privacy-utility trade-offs using Tim Van Erven and Peter Harremoes. Rényi divergence and Kullback-Leibler divergence. IEEE transactions policies. In Proceedings of the 2014 ACM SIGMOD Inon information theory, 60(7):3797–3820, 2014. ternational Conference on Management of data, pages 1447–1458, 2014. Martin J. Wainwright and Michael I. Jordan. Graphical models, exponential families, and variational inference. Alberto Holly, Alain Monfort, and Michael Rockinger. Found. Trends Mach. Learn., 1(1–2):1–305, January Fourth order pseudo maximum likelihood methods. 2008. Journal of Econometrics, 162(2):278–293, 2011. Zach Jorgensen, Ting Yu, and Graham Cormode. Con- Yu-Xiang Wang, Borja Balle, and Shiva Prasad Kasiviswanathan. Subsampled Rényi differential privacy servative or liberal? Personalized differential privacy. 9

Task-aware Kernel Stein certificates for Rényi differential privacy

and analytical moments accountant. In The 22nd international conference on artificial intelligence and statistics, pages 1226–1235. PMLR, 2019. George Wynne. Contributions in Functional Data Analysis and Functional-Analytic Statistics. PhD thesis, Imperial College London, March 2023. Wanrong Zhang, Olga Ohrimenko, and Rachel Cummings. Attribute privacy: Framework and mechanisms. In Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency, pages 757– 766, 2022.

Checklist 1. For all models and algorithms presented, check if you include: (a) A clear description of the mathematical setting, assumptions, algorithm, and/or model. [Yes] (b) An analysis of the properties and complexity (time, space, sample size) of any algorithm. [Not Applicable] (c) (Optional) Anonymized source code, with specification of all dependencies, including external libraries. [Yes] 2. For any theoretical claim, check if you include: (a) Statements of the full set of assumptions of all theoretical results. [Yes] (b) Complete proofs of all theoretical results. [Yes] (c) Clear explanations of any assumptions. [Yes] 3. For all figures and tables that present empirical results, check if you include: (a) The code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL). [Yes] (b) All the training details (e.g., data splits, hyperparameters, how they were chosen). [Yes] (c) A clear definition of the specific measure or statistics and error bars (e.g., with respect to the random seed after running experiments multiple times). [Yes] (d) A description of the computing infrastructure used. (e.g., type of GPUs, internal cluster, or cloud provider). [Yes] 4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets, check if you include: (a) Citations of the creator If your work uses existing assets. [Yes] 10

(b) The license information of the assets, if applicable. [Yes] (c) New assets either in the supplemental material or as a URL, if applicable. [Yes] (d) Information about consent from data providers/curators. [Not Applicable] (e) Discussion of sensible content if applicable, e.g., personally identifiable information or offensive content. [Not Applicable] 5. If you used crowdsourcing or conducted research with human subjects, check if you include: (a) The full text of instructions given to participants and screenshots. Not Applicable] (b) Descriptions of potential participant risks, with links to Institutional Review Board (IRB) approvals if applicable. [Not Applicable] (c) The estimated hourly wage paid to participants and the total amount spent on participant compensation. [Not Applicable]

KSD Setup

In this section we provide the technical details for the setup of kernel Stein discrepancies. In particular we provide assumptions for (3) in the main text to hold. We recall that we assume P to be a probability measure on Rd with smooth positive density p and Q to be a probability measure on Rd . We start by defining the Stein class of P . A function ϕ : Rd → Rd is in the Stein class of P if • ϕ ∈ C 1 (Rd , Rd ); • the vector field pϕ is integrable and its integral over spheres vanishes: Z lim p(x)ϕ(x) · n(x)dS(x) = 0, R→∞

∂BR (0)

where BR (0) denotes the ball of radius R centred at 0 and n(x) is the unit normal vector at x, with S the surface measure on ∂BR (0); • EP |TP ϕ(x)| < ∞. Let K : Rd × Rd → Rd×d be a vector-valued, symmetric positive semi-definite kernel and let HK denote its vectorvalued RKHS. We further assume that K is twice differentiable (i.e. Kij ∈ C 2 (Rd × Rd ) for all 1 ≤ i, j ≤ d). It then follows that HK ⊂ C 1 (Rd ), see (Steinwart and Christmann, 2008, Corollary 4.36). Moreover we assume that EQ |TP ϕ(X)| < ∞ for every ϕ ∈ HK . Then the expression KSDK (P, Q) :=

sup

|EQ [TP ϕ(X)]|

∥ϕ∥HK ≤1

is well-defined. Assume that Q has strictly positive smooth density q and assume in addition to the above that • for every ϕ ∈ HK , one has that ϕ is in the Stein class of Q; • it holds that

q EQ

(sP (X) − sQ (X))⊤ K(X, X)(sP (X) − sQ (X)) < ∞.

(12)

Then (3) holds. This is shown in Supplementary Material B.5.1 of Barp et al. (2019); for the one-dimensional setting see also (Liu et al., 2016, Lemma 2.3 & Theorem 3.8). For further RKHS formulations, including double-expectation or spectral representations of KSD, see for example Chapter 5 in Wynne (2023) and Liu et al. (2016); Chwialkowski et al. (2016). For completeness here we provide a proof. Proposition A.1. Assume that P , Q, and K satisfy the conditions stated above, including that every ϕ ∈ HK belongs to the Stein class of Q and that Condition 12 holds. Then, for independent X, Y ∼ Q, KSDK (P, Q)2 = EX,Y ∼Q (sP (X) − sQ (X))⊤ K(X, Y )(sP (Y ) − sQ (Y )) . Proof. Set b(x) := sP (x) − sQ (x) and w(x) := b(x)⊤ K(x, x)b(x)

1/2

, and note that Assumption (12) states that

C := EQ [w(X)] < ∞. For x ∈ Rd , the vector-valued reproducing property gives that K(·, x)b(x) ∈ HK , that ∥K(·, x)b(x)∥HK = w(x), and that b(x)⊤ ϕ(x) = ⟨K(·, x)b(x), ϕ⟩HK . Hence, for every ϕ ∈ HK , EQ |b(X)⊤ ϕ(X)| ≤ C∥ϕ∥HK . Thus Λ(ϕ) := EQ [b(X)⊤ ϕ(X)] is a bounded linear functional on the real Hilbert space HK . Moreover, since ϕ belongs to the Stein class of Q, Z EQ [(TQ ϕ)(X)] = lim q(x)ϕ(x) · n(x) dS(x) = 0. R→∞

∂BR (0)

Task-aware Kernel Stein certificates for Rényi differential privacy

Using TP ϕ = TQ ϕ + b⊤ ϕ, we obtain EQ [(TP ϕ)(X)] = Λ(ϕ). By the Riesz representation theorem, there is a unique h ∈ HK such that Λ(ϕ) = ⟨h, ϕ⟩HK

for all ϕ ∈ HK ,

∥h∥HK ≤ C.

We next identify this representer pointwise. For every y ∈ Rd and a ∈ Rd , applying the reproducing property and the definition of Λ yields a⊤ h(y) = ⟨h, K(·, y)a⟩HK = Λ(K(·, y)a) = EQ [b(X)⊤ K(X, y)a] = a⊤ EQ [K(y, X)b(X)]. The expectation is finite: by the reproducing property and Cauchy–Schwarz, 1/2 w(x). |a⊤ K(y, x)b(x)| ≤ a⊤ K(y, y)a Taking a to be each coordinate vector establishes componentwise absolute integrability with respect to EQ . Hence h(y) = EQ [K(y, X)b(X)],

y ∈ Rd .

In particular, the pointwise expectation above is an element of HK , because it equals the Riesz representer already constructed. The variational definition of KSD now gives KSDK (P, Q) =

sup

|⟨h, ϕ⟩HK | = ∥h∥HK .

∥ϕ∥HK ≤1

The last equality follows from Cauchy–Schwarz, with equality at ϕ = h/∥h∥HK when h ̸= 0; when h = 0, both sides vanish. Finally, for all x, y ∈ Rd , |b(x)⊤ K(x, y)b(y)| = ⟨K(·, x)b(x), K(·, y)b(y)⟩HK ≤ w(x)w(y). For independent X, Y ∼ Q, the expectation of the right-hand side equals C 2 < ∞. Thus Fubini’s theorem applies, and ∥h∥2HK = Λ(h) = EX [b(X)⊤ h(X)] = EX,Y ∼Q [b(X)⊤ K(X, Y )b(Y )]. Combining the last two displays proves the assertion. An example in which P does not have a smooth density p is that of the Laplace distribution, for which the density is continuous, and differentiable everywhere except at 0. Pike and Ren (2014) show that for W ∼ Laplace(0, b), 1 E sgn(W )g(W ) b for all absolutely continuous functions g for which these expectations exist, where sgn is the sign function; this is the weak integration by parts formula. Thus, the score function in the weak sense is sb (x) = − sgn(x)/b. As in the proof of Proposition A.1, all relevant arguments are in expectation, we deduce that the conclusion of Proposition A.1 also holds for the Laplace distribution. Eg ′ (W ) =

Proofs omitted from previous sections

B.1

Proofs left out in Section 3

In order to prove Proposition 3.1, we start by providing a stronger result that holds for more general flows Tt . In the following, we denote by Jft (x) the spatial Jacobian with entries [Jft (x)]i,j = ∂xi ∂xj ft (x), for any differentiable function f : R × Rd → Rd : (t, x) 7→ ft (x). Proposition B.1 (First variation of Rényi divergence). Let ϕ : Rd → Rd be a C 1 function, let ϵ > 0, and let the function T : (−ϵ, ϵ) × Rd → Rd be such that • ∂t Tt (x) and J∂t Tt (x) exist and are continuous in (t, x); • for every t ∈ (−ϵ, ϵ), the function Tt : Rd → Rd is a diffeomorphism; 12

Task-aware Kernel Stein certificates for Rényi differential privacy

• T0 (x) = x for all x ∈ Rd ; • ∂t Tt |t=0 = ϕ. Define Qt := (Tt )# Q and denote its density by qt . We assume in addition that • there exists a function G ∈ L1 (Rd ) such that qt (x)α − q(x)α ≤ G(x) t

(13)

q(x)α p(x)1−α |ϕ(x)|dx < ∞;

(14)

p(x)1−α for all x ∈ Rd and t ∈ (−ϵ, ϵ); • we have

Z Rd

• and

q(x)α p(x)1−α |ϕ⊤ ∇ log

Then

p(x) q(x)

|dx < ∞.

d Dα (Qt ∥P ) = −EQα|P TP ϕ . dt t=0

(15)

(16)

Proof. We start by claiming that the density qt of Qt satisfies ∂t qt |t=0 = −∇ · (qϕ). We have qt (y) = q(Tt−1 (y)) det(JTt (Tt−1 (y)))−1 . Thus, ∂t qt (y)|t=0 = ∂t q(Tt−1 (y)) t=0 det(JT0 (T0−1 (y)))−1 + q(T0−1 (y)) ∂t det(JTt (Tt−1 (y)))−1 t=0 . Note that T0 = T0−1 is the identity function, and hence JT0 = Id and T0−1 (y) = y. It follows that ∂t qt (y)|t=0 = ∂t q(Tt−1 (y)) t=0 + q(y) ∂t det(JTt (Tt−1 (y)))−1 t=0 .

(17)

By the chain rule we have that ∂t Tt−1 (y) t=0 = −[JT0 (T0−1 (y))]−1 ∂t Tt t=0 (T0−1 (y)) = −ϕ(y). It follows that

∂t q(Tt−1 (y)) t=0 = ∇q(T0−1 (y))⊤ ∂t Tt−1 (y) t=0 = −∇q(y)⊤ ϕ(y).

(18)

∂t det(JTt (Tt−1 (y)))−1 t=0 . −1

We now turn to computing As we did not assume second spatial derivatives for Tt , the quantity det(JTt (Tt−1 (y))) might not be differentiable at every t, but the derivative at zero exists and can be computed. We start by noting that JT0 ≡ Id and by the fundamental theorem of algebra Z t JTt (x) = Id + ∂s JTs (x)ds. 0

By continuity of J∂t Tt , we can swap the order of integration and write Z t JTt (x) = Id + J∂s Ts (x)ds. 0

It follows that for any t ̸= 0, 1 JTt (Tt−1 (y)) − Id = t t

Z t

J∂s Ts (Tt−1 (y))ds =

Z 1 0

J∂s Ts s=tu (Tt−1 (y))du,

where the second line follows by a change of variables. Again by continuity, we can take the limit t → 0 on both sides and inside the integral, to obtain Z 1 ∂t JTt (Tt−1 (y)) t=0 = J∂s Ts |s=0 (T0−1 (y))du = Jϕ (y). 0

Define At := JTt (Tt−1 (y)). We are thus interested in computing ∂t det(At )−1 t=0 . Note that det(A0 ) = det(Id ) = 1 and det(At ) is continuous, so for a small neighbourhood of t = 0, we have det(At ) ̸= 0. 13

Task-aware Kernel Stein certificates for Rényi differential privacy

By the Jacobi formula, we have ∂t det(At ) t=0 = det(At ) tr(A−1 t ∂t At ) t=0 = tr(∂t At t=0 ) = tr(Jϕ (y)) = div ϕ. Now, ∂t det(JTt (Tt−1 (y)))−1 t=0 = −

∂t det(At ) t=0 = − div ϕ. det(A0 )2

(19)

Combining (17), (18) and (19), we obtain ∂t qt (y) t=0 = −∇q(y)⊤ ϕ(y) + q(y)(− div ϕ(y)) = −∇ · (qϕ)(y), which proves the claim. R Writing Zα (t) := Rd qtα (x)p1−α (x) dx, Condition (13) allows us to differentiate under the integral sign and we obtain Z Z d = Zα (t) αq0 (x)α−1 p(x)1−α ∂t qt (x) t=0 dx = −α r(x)α−1 ∇ · (qϕ)(x) dx dt d d R R t=0 Recall that r = q/p and define A(x) := r(x)α−1 ∇ · (qϕ)(x); B(x) := r(x)α p(x)ϕ⊤ ∇ log r(x). R d Zα (t) t=0 = −α Rd A(x)dx, and by condition (13), A ∈ L1 (Rd ). Assumption (15) implies that B ∈ Note that dt L1 (Rd ). Now note that by the chain rule A + (α − 1)B = ∇ · (rα pϕ), and hence ∇ · (rα pϕ) ∈ L1 (Rd ). Since assumption (14) gives us rα pϕ ∈ L1 (Rd ), by integration by parts (and integration using an exhaustion by compact sets) it follows that Z Z A(x) + (α − 1)B(x)dx = ∇ · (rα pϕ)(x)dx = 0 (20) Rd

Moreover, using the chain rule again one sees that Z Z 1 1 EQα|P [TP ϕ(x)] = r(x)α p(x)(∇ · ϕ(x) + ∇ log p(x))⊤ ϕ(x) dx = A(x) − B(x)dx. Zα (0) Rd Zα (0) Rd Since Dα (Qt ∥P ) = (α − 1)−1 log Zα (t), this gives, using (20), Z Z d α 1 Dα (Qt ∥P ) =− A(x)dx = − (A(x) − B(x))dx = −EQα|P [TP ϕ(x)], dt (α − 1)Zα (0) Rd Zα (0) Rd t=0 which proves (16). Proposition 3.1. Assume that for every ϕ ∈ HK , one has ϕ ∈ C 1 (Rd ; Rd ) and supx∈Rd ∥Jϕ (x)∥op < ∞. Assume moreover that Conditions (13)–(15) hold. Then d Dα ((I + tϕ)# Q∥P ) = KSDK (P, Qα|P ). dt t=0 ∥ϕ∥HK ≤1 sup

Proof. This result follows immediately as soon as ϕ ∈ HK and Tt = I +tϕ satisfy the assumptions of Proposition B.1. It is clear that ∂t Tt = ϕ and J∂t Tt = Jϕ exist and are continuous, as well as T0 = I and ∂t Tt t=0 = ϕ. Conditions (13)–(15) follow by definition. It remains to show that for small enough t, the function Tt is a diffeomorphism on Rd . Fix y ∈ Rd and to note that x 7→ y − tϕ(x) is a contraction mapping, since supx∈Rd ∥Jϕ (x)∥op < ∞ implies that ϕ is Lipschitz. By the Banach fixed point theorem, there is a unique x ∈ Rd such that x = y − tϕ(x), hence a unique x ∈ Rd such that Tt (x) = y, implying that Tt is bijective. Moreover, JTt = Id + tJϕ . Since the operator norm of Jϕ is uniformly bounded, Id + tJϕ is invertible, and by the inverse function theorem, JT −1 = JT−1 . t t

Task-aware Kernel Stein certificates for Rényi differential privacy

B.2

Proofs left out in Subsection 4.1

Proposition 4.2 (Escort KSD). Under appropriate conditions (see Appendix A), the KSD based on the kernel K = KB,A satisfies KSDKB,A (P, Qα|P )2 = cB,Σ α2 (Σ−1 δ)⊤ AΣ−1 δ, where cB,Σ := E[kB (X, Y )] = {det(I + 2ΣB −1 )}−1/2 . Proof. We start by showing that, for a general kernel K, the KSD satisfies KSDK (P, Qα|P )2 = EX,Y ∼Qα|P α2 (Σ−1 δ)⊤ K(X, Y )(Σ−1 δ) , (21) where X and Y are independent. We first calculate the density of Qα|P . Note that α 1 1 q(x) α(α−1) ⊤ −1 ⊤ −1 p(x) = exp − (x − mD − αδ) Σ (x − mD − αδ) exp (δ Σ δ) , p(x) 2 2 (2π)d/2 det(Σ)1/2 hence Qα|P = N (mD + αδ, Σ). Furthermore, the score functions are sP (x) = −Σ−1 (x − mD ), and sQα|P (x) = −Σ−1 (x − mD − αδ), so that sP (x) − sQα|P (x) = −αΣ−1 δ

(22)

for every x ∈ Rd . Overall, we thus have by (3) that KSDK (P, Qα|P )2 = EX,Y ∼Qα|P (sP (X) − sQα|P (X))⊤ K(X, Y )(sP (Y ) − sQα|P (Y )) = EX,Y ∼Qα|P α2 (Σ−1 δ)⊤ K(X, Y )(Σ−1 δ) , where X and Y are independent. Now let K = KB,A . Using (21) and (22), and observing that the score difference is constant, gives the second iid

statement, where the expression of cB,Σ follows as for X, Y ∼ Qα|P we have X − Y ∼ N (0, 2Σ). Isotropic kernel we obtain

We start with the isotropic kernel KB,Id (x, y) = kB (x, y)Id . Then by Proposition 4.2 with A = Id

KSDKB,Id (P, Qα|P )2 = cB,Σ α2 δ ⊤ Σ−2 δ. (23) 2 −2 −1 The resulting KSD involves a quadratic weight α Σ while the Rényi divergence involves only αΣ , see Proposition 4.1. As the next proposition shows, this mismatch yields a looser upper bound on the Rényi divergence. Proposition B.2. Let λmin (Σ) and λmax (Σ) be the extreme eigenvalues of Σ. Then λmin (Σ) λmax (Σ) KSDKB,Id (P, Qα|P )2 ≤ Dα (Q∥P ) ≤ KSDKB,Id (P, Qα|P )2 , 2αcB,Σ 2αcB,Σ where both inequalities become equalities whenever Σ = σ 2 Id for some σ ∈ R+ . Proof. Diagonalize Σ. Termwise, λmin (Σ) δ ⊤ Σ−2 δ ≤ δ ⊤ Σ−1 δ ≤ λmax (Σ) δ ⊤ Σ−2 δ. Combine this with Proposition 4.1 and (23).

Anisotropic kernel We now consider an anisotropic kernel KB,A by setting A = Σ to match the covariance structure of the privacy mechanism, i.e. KB,Σ (x, y) := kB (x, y)Σ. Theorem 4.3. For the kernel K = KB,Σ we obtain, 1 Dα (Q∥P ) = KSDKB,Σ (P, Qα|P )2 . 2αcB,Σ Thus, if KSDK (P, Qα|P )2 ≤ ϵ uniformly over all neighbourhoods D ∼ D′ then the Gaussian mechanism satisfies (α, 2αcϵB,Σ )-RDP. Proof. By Proposition 4.2, KSDKB,Σ (P, Qα|P )2 = α2 (Σ−1 δ)⊤ E[kB (X, Y )Σ](Σ−1 δ) = α2 E[kB (X, Y )]δ ⊤ Σ−1 δ and thus KSDKB,Σ (P, Qα|P )2 = cB,Σ α2 δ ⊤ Σ−1 δ. A comparison with Proposition 4.1 gives the result. 15

Task-aware Kernel Stein certificates for Rényi differential privacy

B.3

Proofs left out in Subsection 4.2

Proposition 4.5 (Rényi divergence). For P , Q the Laplace output distributions of a neighbouring dataset pair (D, D′ ), δ . Dα (Q∥P ) = Dα (P ∥Q) = Rα b δ

In particular, D1 (Q∥P ) = δb + e− b − 1, and D∞ (Q∥P ) = δb . Proof. By translation invariance, take mD = 0 and define Zα,δ,b :=

R R

q(x)α p(x)1−α dx. Let qδ be the density of

1 Qδ = Lap(δ, b) and note that as mD = 0 we have Q = Qδ . Furthermore, qδ (x) = 2b exp − |x−δ| b

= q−δ (−x)

while p(x) = q0 (x) = p(−x) which implies that Dα (Q∥P ) = Dα (Qδ ∥P ) = Dα (Q−δ ∥P ). In particular, we may wlog assume that δ > 0. Splitting the integral over (−∞, 0), (0, δ), and (δ, ∞) gives δ

Zα,δ,b =

αe(α−1) b + (α − 1)e−α b . 2α − 1

(24)

Hence the first result follows as Dα (Q∥P ) = (α − 1)−1 log Zα,δ,b . The change of variables x 7→ δ − x interchanges p and q, proving symmetry for this particular location family. The limits α ↓ 1 and α → ∞ give the remaining results; see also (Mironov, 2017, Proposition 6). Remark B.3. If B → ∞ in every direction, then kB → 1 and cB,Σ → 1. The theorem then reduces to the constant covariance-matched kernel KΣ (x, y) = Σ, for which we have the equality Dα (Q∥P ) =

1 α KSDKΣ (P, Qα|P )2 = KSDKΣ (P, Q)2 . 2α 2

In particular, the expression for the Rényi divergence can be already recovered with a constant operator-valued kernel. Proposition 4.6 (Escort KSD). Under the conditions detailed in Appendix A, the KSD based on the scalar kernel k satisfies KSDK (P, Qα|P )2 =

4α2 EX,Y ∼Qα|P k(X, Y )1{X∈Iδ } 1{Y ∈Iδ } , b2

where X and Y are independent and Iδ := (min{mD , mD + δ}, max{mD , mD + δ}. Proof. The escort Qα|P has density dQα|P q(x)α p(x)1−α = , dx Zα,δ,b where the normalization constant Zα,δ,b is given in (24). Furthermore, the corresponding score functions are defined almost everywhere and given by 1 sP (x) = − sgn(x − mD ) b and (1 − α) α sQα|P (x) = − sgn(x − mD ) − sgn(x − (mD + δ)) = (1 − α)sP (x) + αsQ (x), b b so that 2α sP (x) − sQα|P (x) = α(sP (x) − sQ (x)) = − sgn(δ) 1{x∈Iδ } (25) b for almost every x ∈ R. Overall, we thus obtain by (3) that KSDK (P, Qα|P )2 = EX,Y ∼Qα|P (sP (X) − sQα|P (X))⊤ K(X, Y )(sP (Y ) − sQα|P (Y )) 4α2 = 2 EX,Y ∼Qα|P k(X, Y )1{X∈Iδ } 1{Y ∈Iδ } , b where X and Y are independent. 16

Task-aware Kernel Stein certificates for Rényi differential privacy

Gaussian RBF kernel

We start with the normalized Gaussian RBF kernel given by (x − y)2 . kh (x, y) := exp − 2h2

(26)

Furthermore, for ρ := hb define Jα,ρ (u) :=

(2α − 1)2 Cα (u)2

Z uZ u 0

e−(2α−1)(t+s) e−(t−s) /(2ρ ) dt ds,

(27)

where Cα (u) := α + (α − 1)e−(2α−1)u . Proposition B.4. For kh the RBF kernel in (26) we obtain KSDkh (P, Qα|P )2 =

|δ| α2 J . α,ρ 2 b b

Whenever b2 KSDkh (P, Qα|P )2 ∈ [0, Jα,ρ (∞)) ⫋ [0, ∞), we thus have 2 b −1 2 Dα (Q∥P ) = Rα Jα,ρ KSD (P, Q ) . kh α|P α2 Proof. First, note that the RBF kernel fulfils k(x, y) = k(−x, −y). As x ∈ Iδ ⇐⇒ −x ∈ I−δ the expression in Proposition 4.6 is invariant under a sign change of δ. In particular, we may assume wlog that δ > 0. Let x ∈ (mD , mD + δ). Then the escort density is given by |x−mD −δ| |x−mD | x−mD dQα|P δ 1 1 1 1 b (x) = e−α e−(1−α) b = e(2α−1) b e− b . dx 2b Zα,δ,b 2b Zα,δ,b

Applying this to Proposition 4.6 and changing variables to u = (x − mD )/b and v = (y − mD )/b gives Z δb Z δb 2 2 α2 −2α δb 2 2 e(2α−1)(u+v) e−(u−v) /(2ρ ) du dv. b KSDkh (P, Qα|P ) = 2 2 e b Zα,δ,b 0 0 Now note that

δ e(α−1) b e(α−1) b Zα,δ,b = (α + (α − 1)e−(2α−1) b ) = Cα 2α − 1 2α − 1

δ . b

Then substituting s = u − δb and t = v − δb in the above equality yields α2 (2α − 1)2 b KSDkh (P, Qα|P ) = 2 b2 Cα δb 2

Z δb Z δb 0

e−(2α−1)(t+s) e−(t−s) /(2ρ ) ds dt.

To obtain the second statement, we analyze the function Jα,ρ |δ| b . As α > 1, the double integral is increasing while Cα is decreasing. Therefore, Jα,ρ is increasing as |δ| b → ∞. Furthermore, the function starts at Jα,ρ (0) = 0 and saturates at √ 2π ρ (2α − 1) (2α − 1)2 ρ2 Jα,ρ (∞) = exp [1 − Φ ((2α − 1)ρ)] < ∞, α2 2 where Φ denotes the standard normal distribution function. Consequently Jα,ρ has an inverse from [0, Jα,ρ (∞)) to [0, ∞). The inversion above does not yield a useful global linear KSD bound on Rényi divergence. Indeed, Jα,ρ is bounded with Jα,ρ (∞) < ∞ whereas Rα |δ| → ∞ as |δ| b b → ∞. Thus, the KSD based on the RBF kernel loses sensitivity to increasingly large displacements even though the Rényi divergence continues to grow. Thus, while the RBF kernel captures the changes of the Rényi divergence well locally, a different kernel choice is needed to obtain global sensitivity. 17

Task-aware Kernel Stein certificates for Rényi differential privacy

Constant kernel Consider the rank-one kernel k0 (x, y) := 1. Theorem 4.7. For k0 (x, y) ≡ 1, |δ|

KSDk0 (P, Qα|P ) =

|δ|

α e(α−1) b − e−α b . |δ| b αe(α−1) |δ| b + (α − 1)e−α b

Set κα := b KSDk0 (P, Qα|P ) ∈ [0, 1). Then |δ| 1 1 α α−1 Dα (Q∥P ) = Rα = log − log 1 + κα . b 2α − 1 1 − κα (α − 1)(2α − 1) α

(6)

Proof. As in Proposition B.4, we may assume wlog that δ > 0 as the constant kernel fulfils k0 (x, y) = k0 (−x, −y). The escort probability of the interval between the modes is δ

¶X∼Qα|P (mD < X < mD + δ) =

e(α−1) b − e−α b

2 αe(α−1) b + (α − 1)e−α b

Combining this with Proposition 4.6 gives the first equality. By further applying this equality to κα := b KSDk0 (P, Qα|P ) and solving for δb yields δ 1 α + (α − 1)κα = log . b 2α − 1 α(1 − κα ) Finally, applying Proposition 4.5 yields the second equality. Remark B.5. As k0 (x, y) = k0 (−x, −y), we may assume wlog that δ > 0, see the proof of Theorem 4.7. Differentiating 1b Rα (u) and evaluating at the point u = bt yields the right hand side of (6) and thus for Qt = PmD +t , t ∈ [0, δ], we obtain d 1 d Dα (Qt ∥P ) = Rα (u) = KSDk0 (P, (Qt )α|P ). dt du b u= t b

Consequently, integration from 0 to δ gives Z δ Dα (Q∥P ) = Dα (Qδ ∥P ) − Dα (Q0 ∥P ) =

KSDk0 (P, (Qt )α|P ) dt. 0

In particular, the first identity is a realization of Proposition B.1 while the second identity shows a global version thereof. Although both kernel choices kh and k0 yield a bounded KSD, the constant kernel k0 provides an explicit relation between the KSD and the displacement δ that can be inverted analytically. This allows the Rényi divergence to be recovered from the KSD for all δ ≥ 0. For the RBF kernel kh such a relation exists only locally. B.4

Proofs left out in Subsection 4.3

We start with a detailed introduction to the exponential mechanism. Let (Y, F, ν) be a measurable output space equipped with a fixed, data-independent base measure ν. Assume that Y ⊆ Rd and that ν(dy) = h0 (y) dy, with h0 (y) > 0, where h0 is smooth and independent of the dataset. We remark that the need to specify the base measure is essential on non-Euclidean and infinite-dimensional output spaces; see Awan et al. (2019). For a dataset D ∈ D, let uD : Y → R be a measurable utility and let β > 0 be an inversetemperature parameter. Define the exponential mechanism by PD (dy) = pD (y) ν(dy),

pD (y) :=

exp{βuD (y)} , exp(A(u0 ))

where A is the (general) log-partition function defined by Z A(ut ) := log exp β uD (y) + tδ(u)(y) ν(dy). Y

We assume throughout that every partition function appearing below is finite. 18

(28)

(29)

Task-aware Kernel Stein certificates for Rényi differential privacy

We now fix an ordered neighbouring pair (D, D′ ) and write P := PD , Q := PD′ , and δ(u) := uD′ − uD . Then exp{βδ(u)(y)} dQ (y) = . dP EP [exp{βδ(u)(Y )}] In the following we focus on the regular natural exponential family that can be obtained by setting β = 1 and uD (y) = T uηD (y) := ηD T (y) where ηD ∈ H is the natural parameter corresponding to the dataset D, H ⊂ Rr is an open set and T is a sufficient statistic T : Rd → Rr that is assumed to be differentiable. We denote Pη ( dy) = pη (y)ν( dy) = pη (y)h0 (y) dy for pη (y) := exp{η T T (y) − A(η)}, (30) where A is again the log-partition function defined in (29) and, with a slight abuse of notation, we write A(ηt ) := A((uη )t ). Then the Fisher information matrix is I(ηt ) = ∇2 A(ηt ). We assume that the exponential family is minimal, so that I(η) is positive definite for every η ∈ H. For the fixed ordered neighbouring pair (D, D′ ) set η = ηD , η ′ = ηD′ and δ = ηD′ − ηD , and define ηt := η + tδ. Then δ(u)(y) = δ T T (y). Finally, we assume that ηt ∈ H for any t ∈ [0, α]. We now prove an expanded version of Proposition 4.9. Proposition 4.9 (Rényi divergence). Let P = Pη be a member of the natural exponential family defined above. Then for every α > 1 for which A(uα ) < ∞, α ¯ A(ηα ) − αA(η1 ) + (α − 1)A(η0 ) α = δ ⊤ I((η t )t=0 )δ α−1 2 n R o Rα ¯ t )α ) := 2 1 tI(ηt ) dt + 2 with I((η (α − t)I(η ) dt . t t=0 α 0 α(α−1) 1 Dα (Q∥P ) =

The scaling in (10) is motivated by

R1 0

1 t dt + α−1

Rα 1

(10)

(α − t) dt = α2 .

Proof. The first equality is a standard result for Rényi divergence within the natural exponential family and can, for example, be found in (15) of Thierrin et al. (2022) or in (Wang et al., 2019, Appendix I). For completeness we include a proof below, together with the second representation in terms of the Fisher information. Using (28), α Z Z dQ dP = pD′ (y)α pD (y)1−α ν(dy) = exp {A(uα ) − αA(u1 ) + (α − 1)A(u0 )} . dP Taking (α − 1)−1 times the logarithm gives the first equality in (9). Now let P = Pη be a member of the natural exponential family. Then A(ηα ) − αA(η1 ) + (α − 1)A(η0 ) α−1 Z 1 = [tδ ⊤ ∇A(ηt )]10 − δ ⊤ ∇A(ηt ) dt +

Dα (Q∥P ) =

Z 1

Z α 1 ⊤ [(α − t)δ ⊤ ∇A(ηt )]α + δ ∇A(η ) dt t 1 α−1 1

Z α 1 (α − t)δ ⊤ ∇2 A(ηt )δ dt α − 1 1 0 Z 1 Z α 1 = tδ ⊤ I(ηt )δ dt + (α − t)δ ⊤ I(ηt )δ dt α−1 1 0 Z Z α o α ⊤n 2 1 2 = δ tI(ηt ) dt + (α − t)I(ηt ) dt δ. 2 α 0 α(α − 1) 1

tδ ⊤ ∇2 A(ηt )δ dt +

Proposition 4.10. (Escort KSD) Let P = Pη be a member of the natural exponential family (7). Under the conditions laid out in Appendix A KSDK (P, Qα|P )2 = α2 δ T GK (ηα )δ. 19

Task-aware Kernel Stein certificates for Rényi differential privacy

Proof. First, note that the escort Qα|P is given by Qα|P (dy) ∝ exp β (1 − α)uD (y) + αuD′ (y) ν(dy) and can thus be viewed as a member of the exponential family with function uα,D,D′ (y) := uD (y) + α(uD′ (y) − uD (y)) and base measure ν(dy) = h0 (y) dy, i.e. Qα|P = Puα,D,D′ . Furthermore, the corresponding score functions are given by sP (y) = β∇uD (y) + ∇ log h0 (y) and sQα|P (y) = β∇uα,D,D′ (y) + ∇ log h0 (y). Thus, the base-measure contribution cancels in the score function comparison and we obtain sP (y) − sQα|P (y) = −α β∇δ(u)(y). Overall, we thus have by (3) that KSDK (P, Qα|P )2 = EX,Y ∼Qα|P (sP (X) − sQα|P (X))⊤ K(X, Y )(sP (Y ) − sQα|P (Y )) = α2 β 2 EX,Y ∼Qα|P ∇δ(u)(X)T K(X, Y )∇δ(u)(Y ) . Now let P = Pη . Then ∇δ(u) = JT (y)T δ, where JT (y) ∈ Rr×d is defined as the Jacobian of T . Thus, as β = 1 and Qα|P = Pηα , KSDK (P, Qα|P )2 = α2 δ T GK (ηα )δ. Theorem 4.13. Under Assumptions 4.11 and 4.12 we have CH Dα (Q||P ) ≤ KSDK (P, Qα|P )2 . 2ακH

(11)

Thus, if KSDK (P, Qα|P )2 ≤ ϵ uniformly over all neighbourhoods D ∼ D′ then the exponential mechanism satisfies (α, 2αCHκH ϵ)-RDP. Proof. As T is a sufficient statistic, we have that for any η ∈ H the Fisher information fulfils the identity I(η) = ∇2 A(η) = CovPη (T (X)), see also (Wainwright and Jordan, 2008, Corollary 3.1). In particular, δ ⊤ I(η)δ = δ ⊤ CovPη (T (X))δ = CovPη (δ ⊤ T (X)) = VarPη (δ ⊤ T (X)). Thus, by Proposition 4.9 we have Z Z α o α ⊤n 2 1 2 Dα (Q∥P ) = δ tI(ηt ) dt + (α − t)I(ηt ) dt δ 2 α 0 α(α − 1) 1 Z 1 Z α n o α 2 2 ⊤ = t VarPηt δ T (X) dt + (α − t) VarPηt δ ⊤ T (X) dt 2 α 0 α(α − 1) 1 Z Z α o α CH n 2 1 2 2 2 tEPηt JT (X)⊤ δ dt + (α − t)EPηt JT (X)⊤ δ dt ≤ 2 α 0 α(α − 1) 1 α CH ¯ = J((ηt )α t=0 ) 2 α CH ⊤ ≤ δ GK (ηα )δ 2 κH CH = KSDK (P, Qα|P )2 2α κH where the two inequalities are a consequence of Assumption 4.11 and 4.12, while the last equality follows from Propostition 4.10. Corollary 4.15 (Laplace family). Let Pη = Lap(0, −η −1 ), η ∈ H ⊂ R<0 , be the centered Laplace family, written in natural form as pη (x) = exp(η |x| − A(η)) = − η2 eη|x| with sufficient statistic T (x) = |x| and Lebesgue base measure. Assume that H is chosen such that ηmin ≤ ηt ≤ ηmax < 0 for all t ∈ [0, α] and let K(x, y) = k(x, y) = xy. η2 Then KSDK (P, Qα|P )2 ≤ ϵ uniformly over all D ∼ D′ implies (α, 2αηmin ϵ)-RDP. 2 max

Task-aware Kernel Stein certificates for Rényi differential privacy

Proof. We study P = Pη = Lap(0, −η −1 ), η ∈ H ⊂ R<0 , which belongs to the regular natural exponential family with sufficient statistic T (x) = |x| and Lebesgue base measure ν( dx) = dx. Then pη (x) = exp(η |x| − A(η)) = − η2 eη|x| . We remark that this construction is different to the Laplacian mechanism discussed in Subsection 4.2. We show that Assumptions 4.11 and 4.12 are satisfied with CH = η21 and κH = η21 . Consequently, an application max min of Theorem 4.13 yields 2 ηmin KSDK (P, Qα|P )2 Dα (Q||P ) ≤ 2 2αηmax and the claim follows. As Pλ belongs to the Laplace family, and T (x) = |x|, we have for every δ that VarPη (δ|X|) = EPη [(JT (X)δ)2 ] = δ 2 . Hence Assumption 4.11 holds uniformly with CH = η21 .

δ2 η2

and

max

For Assumption 4.12, consider the positive semidefinite kernel k(x, y) = xy. Since JT (x) = sgn(x) almost everywhere, we have GK (ηα ) = E

iid

X,Y ∼ Pηα

[sgn(X)XY sgn(Y )] = EPηα |X|

1 ηα 2

On the other hand, EPηα |JT (X)δ|2 = δ 2 for every t ∈ [0, α] and thus Z α o n2 Z 1 2 2 ¯ t )α tδ dt + (α − t)δ 2 dt = δ 2 . J((η ) = t=0 α 0 α(α − 1) 1 −2 Since GK (ηα ) ≥ ηmin , it follows that

2 2 ¯ t )α J((η t=0 ) ≤ ηmin δ GK (ηα ).

Thus, Assumption 4.12 holds with κH = η21 . Overall, Theorem 4.13 thus yields min

Dα (Q||P ) ≤

2 ηmin KSDK (P, Qα|P )2 . 2 2αηmax

Corollary 4.16 (Gaussian family). Let P = Pη belong to the Gaussian natural exponential family with sufficient statistic T (x) = x, base measure ν = N (a, Σ) for a ∈ Rd and Σ ≻ 0. Set K(x, y) = ψ(∥x − y∥)Id for some ψ : R → R+ . Then, for λmax (Σ) the largest eigenvalue of Σ and κH = EZ∼N (0,2Σ) [ψ(∥Z∥)], a bound max (Σ) KSDK (P, Qα|P )2 ≤ ϵ uniformly over all D ∼ D′ implies (α, λ2α κH ϵ)-RDP. Proof. Let pη (x) = exp(η ⊤ x − A(η)) = exp(η ⊤ x − a⊤ η − 12 η ⊤ Ση) and consider the regular natural exponential family Pη = N (a + Ση, Σ) with sufficient statistic T (x) = x and base measure ν = N (a, Σ). In particular, choosing ηD = Σ−1 mD and a = 0 recovers the Gaussian mechanism, see Subsection 4.1. We show that Assumptions 4.11 and 4.12 are satisfied with CH = λmax (Σ) and κH = ck = EX,Y ∼N (0,2Σ) [k(X, Y )] such that an application of Theorem 4.13 yields Dα (Q||P ) ≤

λmax (Σ) KSDK (P, Qα|P )2 2αck

which implies the claim. Clearly, JT (x) ≡ Id is constant. Thus, 2 2 VarPηt δ ⊤ T (X) = δ ⊤ Σδ ≤ λmax (Σ) ∥δ∥ = λmax (Σ) EPηt JT (X)⊤ δ and thus Assumption 4.11 is fulfilled with CH = λmax (Σ) the largest eigenvalue of Σ. 2 2 ¯ t )α ) = ∥δ∥2 , see the proof of For Assumption 4.12 , note that EPηt JT (X)⊤ δ = ∥δ∥ again implies J((η t=0 Corollary 4.15. Furthermore, we have GK (ηα ) = E [k(X, Y )] Id . Thus, taking a scalar kernel K(x, y) = iid X,Y ∼ Pηα

k(x, y)Id for which GK (ηα ) = ck Id is constant with some ck > 0, Assumption 4.12 is satisfied with ηH = ck . This kernel assumption includes the constant kernel k(x, y) ≡ 1 with ck = 1 or a translation invariant kernel k(x, y) = ψ(∥x − y∥) as X − Y ∼ N (0, 2Σ) independently of ηα such that ck = EZ∼N (0,2Σ) [ψ(∥Z∥)]. 21

Task-aware Kernel Stein certificates for Rényi differential privacy

As all assumptions are satisfied, Theorem 4.13 yields λmax (Σ) Dα (Q||P ) ≤ KSDK (P, Qα|P )2 . 2αck Corollary 4.16 illustrates that Assumption 4.11 introduces some looseness compared with the mechanism-specific results of Subsection 4.1, but allows the certificate to apply to a substantially broader class of mechanisms. Corollary 4.17 (Quartic family). Let to the natural exponential family with sufficient statistic T (x) = P = Pη belong γ Pd 1 ⊤ 4 x and base density h0 (x) ∝ exp − 2 x Σx − 4 i=1 xi , for some Σ ≻ 0 and γ > 0. Consider the constant kernel K(x, y) = Id and let λmin (Σ) be the smallest eigenvalue of Σ. Then KSDK (P, Qα|P )2 ≤ ϵ uniformly over all ϵ D ∼ D′ implies (α, 2αλmin (Σ) )-RDP. Proof. Let pη (x) = exp η ⊤ x − A(η) with Z A(η) = log

d 1 γX 4 exp(η ⊤ x − x⊤ Σx − x )dx 2 4 i=1 i Rd

for some symmetric Σ ≻ 0 and γ > 0. Set T (x) = x and consider the base measure ν(dx) = h0 (x) dx with ! d 1 ⊤ γX 4 x . h0 (x) = exp − x Σx − 2 4 i=1 i Then for any η ∈ H the corresponding regular natural exponential family is given by ! d X 1 γ Pη ( dx) = exp η ⊤ x − A(η) − x⊤ Σx − x4 dx = pη (x)h0 (x) dx. 2 4 i=1 i We show that the Assumptions 4.11 and 4.12 are satisfied with CH = (λmin (Σ))−1 , and κH = 1. Consequently, an application of Theorem 4.13 yields 1 Dα (Q∥P ) ≤ KSDK (P, Qα|P )2 2αλmin (Σ) and thus the claim. We first show that Assumption 4.11 is satisfied using the Brascamp–Lieb inequality, see (Bakry et al., 2014, Section 4.9.2). We consider the negative log density W = − log(pη h0 ) of Pη . First, note that d γX 4 1 x W (x) = − log(pη (x)h0 (x)) = −η ⊤ x + x⊤ Σx + 2 4 i=1 i

is smooth and differentiating twice gives ∇2 W (x) = −∇2 log(pη (x)h0 (x)) = Σ + 3γ diag(x21 , . . . , x2d ) ⪰ λmin (Σ)Id , where λmin (Σ) > 0 denotes the smallest eigenvalue of Σ that is strictly positive as Σ ≻ 0. Thus, the negative log density is convex. By the Brascamp–Lieb inequality, see (Bakry et al., 2014, Section 4.9.2), it follows that 1 VarPη (f ) ≤ EP ∥∇f (X)∥2 , λmin (Σ) η for every sufficiently smooth function f : Rd → R. In particular, taking f (x) = δ ⊤ T (X), Assumption 4.11 is satisfied with CH = λmin1(Σ) . For Assumption 4.12, consider the constant kernel K(x, y) = Id . Then as JT (x) = Id , GK (ηα ) = E JT (X)K(X, Y )JT (Y )⊤ = Id . iid X,Y ∼ Pηα

¯ t )α ) = ∥δ∥2 , see the proof of Moreover, EPηt JT (X)⊤ δ = ∥δ∥2 for every t ∈ [0, α]. Consequently, J((η t=0 Corollary 4.15. Thus, Assumption 4.12 holds with κH = 1. Overall, an application of Theorem 4.13 yields Dα (Q∥P ) ≤

1 KSDK (P, Qα|P )2 . 2αλmin (Σ)

Task-aware Kernel Stein certificates for Rényi differential privacy

B.5

Additional information for Section 5.1

We start by briefly recalling the Pufferfish framework, which is given by a triple (S, Q, Θ). Here, S is a collection of secrets, where a secret can be interpreted as an event concerning D and is formally defined a measurable subset of D. Furthermore, Q ⊆ S × S is the collection of protected secret pairs. These pairs are ordered as Rényi divergence is asymmetric, i.e. Dα (P ∥Q) ̸= Dα (Q∥P ). In particular, if both orientations are intended, both (si , sj ) and (sj , si ) should be included in Q or verified separately. Finally, Θ indexes a class of data-generating distributions Pθ . We interpret θ ∈ Θ as admissible adversarial prior knowledge. Then for any θ ∈ Θ, Pθ defines the dataset distribution on D and we assume that D ∼ Pθ . In particular, the dataset D is now random under θ ∈ Θ. Let M be a randomized mechanism. For a secret s ∈ S with positive probability under θ, define the secret-conditioned output law Pθ,s := L M (D) | s, θ , D ∼ Pθ . Thus, to sample from Pθ,s , we first sample a dataset D from Pθ conditional on the secret s and then apply the randomized mechanism M . The following remark collects important properties of Rényi Pufferfish privacy. Remark B.6. [Established RPP properties, (Pierquin et al., 2024, Proposition 2.1 and 2.2)] If M is (α, ε)-RPP, then: 1. every deterministic or randomized post-processing of M is also (α, ε)-RPP; 2. for every δ ∈ (0, 1), M is ε + log(1/δ) α−1 , δ -Pufferfish private. Unlike ordinary record-level RDP, RPP does not have a universal mechanism-agnostic adaptive composition theorem. In particular, conditioning on a released transcript updates the adversary’s prior, which may move it outside the declared class Θ. Pierquin et al. (2024) therefore develops privacy amplification by iteration as an alternative for contractive noisy algorithms. To link this framework with escort distributions, fix a prior θ ∈ Θ and define the Pufferfish attainable escort family by n o EαPF (Pθ ) := (Pθ,sj )α|Pθ,si : (si , sj ) ∈ Q; Pθ (sj ) > 0, Pθ (si ) > 0 . (31) The Pufferfish attainable escort family captures the comparison specification imposed by the Pufferfish framework as it contains only escorts generated by the secret comparisons and priors Pθ . It can be far smaller than the set of all probability measures. B.6

Additional information for Subsection 5.3

Theorem 5.3. Let S be a public task subspace with orthonormal basis US ∈ Rd×r and kernel KB,AdS . Then Dα ((US⊤ )# Q∥(US⊤ )# P ) =

1 KSDKB,Ad (P, Qα|P )2 . 2αcB,Σ S

If furthermore Σ−1 δ ∈ S, then Dα (Q∥P ) =

1 KSDKB,Ad (P, Qα|P )2 . 2αcB,Σ S

Proof. As P and Q are Gaussians, we obtain (US⊤ )# P ∼ N (US⊤ mθ,si , US⊤ ΣUS )

and

(US⊤ )# Qα|P ∼ N (US⊤ (mθ,si + αδ), US⊤ ΣUS ).

Note that the adapted covariance ΣS := US⊤ ΣUS ∈ Rr×r is positive definite, i.e. US⊤ ΣUS ≻ 0. We then choose K = KB,A with ⊤ d×d A = AdS = (ΣUS )Σ−1 S (ΣUS ) ∈ R ⊤ to obtain a positive-semidefinite matrix of the correct dimension. As A fulfils Σ−1 AΣ−1 = US Σ−1 S US , an application of Propositions 4.1 and 4.2 analogous to Theorem 4.3 yields the first claim.

Task-aware Kernel Stein certificates for Rényi differential privacy

Now assume that Σ−1 δ ∈ S. Then as range(US = S, there exist a v ∈ Rr such that Σ−1 δ = US v. Then by Proposition 4.2, KSDKB,Ad (P, Qα|P )2 = cB,Σ α2 (Σ−1 δ)⊤ AdS Σ−1 δ S

⊤ = cB,Σ α2 v ⊤ US⊤ (ΣUS )Σ−1 S US ΣUS v

= cB,Σ α2 v ⊤ ΣS Σ−1 S ΣS v = cB,Σ α2 v ⊤ ΣS v = cB,Σ α2 δ ⊤ Σ−1 δ and the claim follows from Proposition 4.1. B.7

Additional information for Subsection 5.4

Assumption 4.11a. Assume that there exist a constant 0 < CH < ∞ such that, for every η ∈ H, every δ ∈ ∆Q η and every t ∈ [0, α], 2 VarPηt δ ⊤ T (X) ≤ CH EPηt JT (X)⊤ δ . Assumption 4.12a. Assume that there exists a constant κH > 0 such that, for every η ∈ H and every δ ∈ ∆Q η , 1 ⊤ ¯ t )α J((η δ GK (ηα )δ, t=0 ) ≤ κH ¯ t )α ) is defined in Assumption 4.12. where J((η t=0 Proposition 5.6. Let S be a public task subspace with projector US and define KS (x, y) := k(x, y)US US⊤ to be a task-aware kernel with scalar kernel k. Assume that Assumptions 4.11a and 4.12a are satisfied with K = KS . Then Dα (Q∥P ) ≤

CH KSDKS (P, Qα|P )2 . 2α κH

A uniform bound on KSDKS for all θ ∈ Θ and (si , sj ) ∈ Q implies the corresponding RPP guarantee. Proof. Follows directly from Theorem 4.13 by replacing Pη by Pθ,s . Corollary 5.8. Let P = Pθ,s belong to the natural exponential family with sufficient statistic T (x) = 12 (a⊤ x)2 ∈ R, x ∈ Rd and a ∈ Rd such that ∥a∥ = 1, and base density h0 (x) as in Corollary 4.17. Let S = span(a) be the ⊤ −1 −1 public task subspace. Assume that ∆Q a) . η ⊂ R+ for all η ∈ H and that ηmax := sup η∈H (η + αδ) < (a Σ δ∈∆Q η

ϵCH Then, KSDKS (P, Qα|P ) ≤ ϵ uniformly over all θ ∈ Θ and (si , sj ) ∈ Q implies (α, 2α κH )-RPP, where CH = a⊤ (Σ − aηmax a⊤ )−1 a and κH = inf η∈H EX∼Pη+αδ [(a⊤ X)2 ]. 2

δ∈∆Q η

Proof. Fix a pair of secrets (s0 , s1 ) ∈ Q and recall that η = ηθ,s0 while δ = ηθ,s1 − ηθ,s0 ∈ ∆Q η such that η + δ = ηθ,s1 . Set P = Pθ,s0 = Pη and Q = Pθ,s1 = Pη+δ . Then the order-α escort is Qα|P = Pη+αδ . We show that −1 m2 Assumptions 4.11a and 4.12a are fulfilled with constants CH = a⊤ Σ − ηmax aa⊤ a and κH = m¯αα , where mt = R R 1 α 2 EPη+tδ [(a⊤ X)2 ], t ∈ [0, α] and m̄α = α2 0 tmt dt + α(α−1) (α − t)mt dt. Then, an application of Proposition 5.6 1 yields Dα (Q∥P ) ≤

CH KSDKS (P, Qα|P )2 2α κH

and the claim follows. max ⊤ −1 −1 We first study the more general case of ∆Q a) we have that η ⊂ R. As ηη,δ := max{η, η + αδ} < (a Σ max Σ − (η + tδ)aa⊤ ≻ Σ − ηη,δ aa⊤ =: Bη,α ≻ 0

(32)

Task-aware Kernel Stein certificates for Rényi differential privacy

uniformly for t ∈ [0, α]. The negative log-density Wt of Pη+tδ , t ∈ [0, α], given by Wt (x) =

d 1 ⊤ γX 4 x (Σ − (η + tδ)aa⊤ )x + x 2 4 j=1 j

is smooth and differentiating twice gives ∇2 Wt (x) = Σ − (η + tδ)aa⊤ + 3γ diag(x21 , . . . , x2d ) ⪰ Bη,α ≻ 0. Thus, the negative log density is convex. By the Brascamp-Lieb inequality, see (Bakry et al., 2014, Section 4.9.2), it follows that −1 VarPη+tδ (f ) ≤ EPη+tδ [∇f (X)⊤ Bη,α ∇f (X)] for all f : Rd → R that are in L2 (Pν ). In particular, taking f (x) = δT (x) = 2δ (a⊤ x)2 and thus ∇f (x) = δa⊤ xa, which yields −1 −1 VarPη+tδ (f ) ≤ a⊤ Bη,α aEPη [δ 2 (a⊤ Xa)2 ] = a⊤ Bη,α aEPη [(JT (X)δ)2 ]. −1 max In particular, Assumption 4.11a is fulfilled with CH = a⊤ Σ − ηmax aa⊤ a, where ηmax = supη∈H,δ∈∆Q ηη,δ . η

Furthermore, note that JT (x)δ = δ a⊤ xa ∈ S. Thus, the specified privacy directions all fall into the task-aware subspace. Furthermore, as S = span(a), we have US = a. Taking the scalar kernel ka (x, y) = (a⊤ x)(a⊤ y), we obtain KS = ka (x, y)US US⊤ = (a⊤ x)(a⊤ y)aa⊤ , see Proposition 5.6. Then as ∥a∥ = 1, GS (η + tδ) = EX,Y ∼Pη+tδ JT (X)KS (X, Y )JT (Y )T = EX,Y ∼Pη+tδ a⊤ Xa(a⊤ X)(a⊤ Y )a⊤ a(a⊤ Y a)T = EX,Y ∼Pη+tδ (a⊤ X)2 (a⊤ Y )2 2 = EX∼Pη+tδ (a⊤ X)2 = m2t . On the other hand, we observe that EPη+tδ JT (X)⊤ δ

= δ 2 EPη+tδ [(a⊤ X)2 ] and thus we obtain

Z α o n Z 1 2 ¯ + tδ)α ) = δ 2 2 tm dt + (α − t)m dt = δ 2 m̄α . J((η t t t=0 α 0 α(α − 1) 1 m2

Then Assumption 4.12a is fulfilled with κH = m̄αα . Under the assumption that ∆Q η ⊂ R+ we can obtain a simpler > 0, we have bound as follows. As δ ∈ ∆Q η d d d mt = Eη+tδ [(a⊤ X)2 ] = 2 Eη+tδ [T (X)] = 2δ∇2 A(η + tδ) = 2δ Varη+tδ (T (X)) ≥ 0. dt dt dt Hence, mt is non-decreasing in t and thus mt ≤ mα for all t ∈ [0, α]. Consequently, Z α o n2 Z 1 2 m̄α ≤ mα t dt + (α − t) dt = mα . α 0 α(α − 1) 1 Thus Assumption 4.12a is also satisfied with κH = mα . The claim now follows with Proposition 5.6.

Numerical illustrations

To illustrate the KSD certificates developed in Sections 4 and 5, we compare R’enyi divergence with escort KSD quantities in several controlled settings. The experiments were carried out on a Dell laptop featuring an Intel Core i7-11850H CPU @ 2.50GHz, 32 GB of RAM, and an NVIDIA GeForce MX450 GPU (2 GB dedicated VRAM). The experiments can be reproduced with the code provided under https://anonymous.4open.science/r/KSD_Renyi_DP-495A/. Where randomness is controlled by a fixed random seed, the corresponding seed is specified in the code. 25

Task-aware Kernel Stein certificates for Rényi differential privacy

Figure 2: Numerical validation of Theorem 4.3: varying the size of the displacement C.1

Gaussian mechanism: kernel choice

We first use the Gaussian mechanism, for which both Rényi divergence and the escort KSD are available in closed form, to illustrate how the kernel choice affects the tightness of the KSD certificate. With the notation in Subsection 4.1 we use Σ=

0.5 0

0 2

√ √ (Σ) 2 with condition number κ(Σ)= λλmax = 0.5 = 4, and we use δ = r(1/ 2, 1/ 2)⊤ , a replacement in direction of min (Σ) 45 degrees, with ||δ||2 ∈ [0, 3] for the shift between different output means, equally spaced to get 15 values. The parameter for the Rényi divergence is α = 4. For the isotropic operator-valued kernel in (4) we take B = 4I2 , giving cB,Σ = (5/2)−1/2 = 0.632. Figure 2 confirms that, with the covariance-matched kernel KB,Σ , the identity in Theorem 4.3 holds (up to numerical variation); for large changes ||δ||2 , the isotropic kernel KB,Id gives only a loose upper bound. Figure 3 instead varies the direction of the shift, δ(θ) = (cos(θ), sin(θ))⊤ , keeping the norm fixed at ||δ||2 = 1. It shows that shift in a low-noise direction is easier to detect than an equally large shift in a high-noise direction. With the given Σ the smallest-noise-variance direction is (1, 0), corresponding to the smallest eigenvalue λmin (Σ) = 1/2, giving 0 degrees; the highest-noise-variance direction is (0, 1), corresponding to the largest eigenvalue λmax (Σ) = 2, giving 90 degrees. C.2

Exponential family certificates

We next consider quartic exponential families to illustrate the KSD certificate beyond settings in which the Rényi divergence is readily available in closed form. One-dimensional quartic example A non-Gaussian quartic exponential family pη (x) ∝ exp(ηx − x4 /4), with constant-kernel escort KSDs; for its properties see for example Holly et al. (2011). Here we set the baseline natural parameter to zero so that θ = 0 and we use a constant kernel. In this example, for the Fisher information I(η) = I(−η) has negative derivative for η > 0 and henc has its unique global maximum at η = 0. Thus, from (9) we obtain the bound α (33) Dα (Q∥P ) ≤ δ ⊤ I(0)δ. 2 Γ( 3 ) As I(0) = 2 Γ 14 ≈ 0.6759 has an explicit formula, it can be well approximated numerically. Moreover, in this (4) one-dimensional case, I(0) equals the variance. Instead of using the bound in Corollary 4.17, in this instance we can 26

Task-aware Kernel Stein certificates for Rényi differential privacy

Directional looseness of the isotropic Gaussian KSD certificate 4.0

Certificate / exact RDP

3.5 3.0 Isotropic upper certificate / exact RDP Covariance-matched certificate / exact RDP Worst-case factor ( )

2.5 2.0 1.5 1.0 0

20 30 40 50 60 70 80 Shift angle in the min/max-variance eigenspace 0 degrees = minimum variance; 90 degrees = maximum variance

Figure 3: Numerical validation of Theorem 4.3: varying the angle

Quartic exponential family ( = 4) Exact RDP (numerical quadrature) KSD approximation

0.6 0.5 Value

0.4 0.3 0.2 0.1 0.0 0.0

0.1

0.2

0.3 0.4 0.5 Natural-parameter shift

0.6

0.7

Figure 4: The KSD approximation to RDP for the quartic exponential family. The “exact” RDP is an approximation obtained by numerical quadrature.

directly use that KSDK (P, Qα|P )2 = α2 δ ⊤ δ to obtain the sharper bound Dα (Q∥P ) ≤

I(0) KSDK (P, Qα|P )2 . 2α

Figure 4 shows that this sharper KSD approximation is reasonable for small parameter shifts. This example is another illustration that in special cases, the bound in Corollary 4.17 can be improved. Coupled quartic example In this example we assess the quality of the KSD certificate for the exponential mechanism derived in Subsection 4.3. We focus on a high-dimensional continuous quartic exponential family. In the 27

Task-aware Kernel Stein certificates for Rényi differential privacy

framework of Corollary 4.17 assume that Σ ≻ µId ≻ 0 for some µ > 0 and set γ = 1, and consider the family d n 1 1 X 4o pt (x) ∝ exp (η + tδ)⊤ x − x⊤ Σx − x . 2 4 i=1 i

Then Σ ≻ µId implies λmin (Σ) ≥ µ and Corollary 4.17 yields that Assumptions 4.11 and 4.12 are fulfilled with constant CH = µ1 and κH = 1. In particular, the proof of Corollary 4.17 yields Dα (Q∥P ) ≤

1 α 2 KSDK (P, Qα|P )2 = ∥δ∥2 , 2αµ 2µ

(34)

where the last equality follows from Proposition 4.10 as GK (η) = Id ; see the proof of Corollary 4.17. In particular, evaluating the privacy certificate does not require a normalising constant. To evaluate the tightness of this certificate, we estimate the Rényi divergence independently by Metropolis-adjusted Langevin sampling at a grid of path parameters and two thermodynamic-integration (TI) identities Rα R1 m(t)dt − α 0 m(t)dt 0 Dα (P1 |P0 ) = , m(t) = Et [δ ⊤ X], (35) α−1 Z α Z 1 1 (α − t)v(t)dt, v(t) = Vart (δ ⊤ X). (36) Dα (P1 |P0 ) = t, v(t)dt + α − 1 1 0 To see this, writing A(θt ) := log Zt , differentiation under the integral sign gives A′ (t) = m(t).With (9) and using Rb A(b) − A(a) = a m(t) dt, we obtain (35). As we integrate over the mean path, we think of this(35) as a meanpath thermodynamic-integration identity. Differentiating once more gives A′′ (t) = VarPt δ ⊤ X . With v(t) := ⊤ VarPt δ X , Taylor’s formula applied to (9) yields (36). We again validate the KSD approximation. In this experiment, we vary α ∈ {1.5, 2, 4, 8}. The matrix Σ = (s+µ)Id − sB ∈ Rd×d is chosen based on the symmetric matrix B with entries 0 on the diagonal and for i ̸= j, Bij = ρ|i−j| with ρ = 0.55, normalised to have spectral radius 1; then Σ − µId = s(Id − B) ≻ 0. We take η = 0, s = 0.4, µ = 0.7, and δ = √1d (1, 1, . . .)⊤ . In Figure 5, d = 20, and the horizontal axis is the Rényi order α. The plot compares three ways of quantifying its order-α Rényi divergence. The dashed line labelled Mean-path TI reference is obtained by estimating m(t) from MCMC samples from Pt , interpolating the estimates over a grid of t-values, and numerically evaluating (35). The solid line with circular markers labelled Variance-path TI reference is obtained by estimating v(t) from the same path samples and numerically evaluating (36). As (35) and (36) are mathematically equivalent, their numerical agreement provides a diagnostic for the accuracy of the MCMC sampling, the path discretisation, the interpolation, and the numerical quadrature. The dash-dotted line labelled Rigorous KSD/strong-convexity bound plots the righthand side of (34). It is a rigorous upper bound, and its distance from the two TI curves shows the conservativeness of the uniform strong-convexity argument. The shaded region is an approximate Monte Carlo uncertainty interval around the mean-path thermodynamic-integration estimate. It is constructed by perturbing the estimated path means m(t) according to their estimated Monte Carlo standard errors, recomputing (35), and taking empirical quantiles of the resulting values. This band is a numerical diagnostic rather than a rigorous confidence band. In particular, it does not fully account for dependence between different path points, interpolation error, quadrature error, MCMC bias, or imperfect mixing. The exact KSD bound is clearly conservative, but of the same order of magnitude. C.3

Task-aware kernel restriction

Finally, we return to the quartic exponential-family setting of Subsection C.2 to illustrate the task-aware KSD certificate of Corollary 5.8. In Example 5.10 we use d = 40, α =∈ {1, 2, 4, 8}, γ = 0.1, δ = 0.1094, and Σ and a are generated such that δa⊤ Σ−1 a = 0.05. The values for a and the entries for Σ were generated at random. The particular instance for a and Σ which is used for Table 1 can be found in the file dense quartic instance.npz in the Outputs folder of the anonymous github site available at https://anonymous.4open.science/r/KSD_Renyi_DP-495A/. As δ > 0, the proof of Corollary 5.8 gives κH = mα and Inequality 32 yields Dα (Q||P ) = Dα (Pη+δ ||Pη ) ≤

αδ 2 CH mα . 2

(37)

Task-aware Kernel Stein certificates for Rényi differential privacy

Coupled quartic RDP, d = 20, = (1, , 1) / d Variance-path TI reference Mean-path TI reference Approximate 95% Monte Carlo interval Rigorous KSD/strong-convexity bound

Estimated RDP

5 4 3 2 1 1

5 Rényi order

Figure 5: Rényi divergence for a fixed neighbouring natural-parameter displacement δ = √1d (1, . . . , 1)⊤ in the coupled quartic exponential family, with d = 20. The solid and dashed curves are numerical RDP estimates obtained from the mathematically equivalent variance-path and mean-path thermodynamic-integration identities (36) and (35). Their agreement provides an MCMC and quadrature diagnostic. The dash-dotted curve is the rigorous strong-convexity/KSD upper bound α∥δ∥22 /(2µ). The shaded region is an approximate Monte Carlo uncertainty interval for the mean-path estimate. Furthermore, since pη (−x) = pη (x) while x 7→ a⊤ x is odd, we obtain EX∼Pη+αδ [a⊤ X] = 0. Thus, mα = VarX∼Pη+αδ (a⊤ X) and applying the Brascamp-Lieb inequality as in the proof of Corollary 5.8 but with f (x) = a⊤ x yields −1 mα = VarX∼Pη+αδ (a⊤ X) ≤ a⊤ Σ − ηmax aa⊤ a = CH . In particular, we obtain the task-unaware coarser fallback bound αδ 2 2 C . (38) 2 H While the KSD can be calculated in closed form, the escort moment mα still has to be estimated numerically; we use MCMC for this task. More details can be found in the file dense quartic metadata.json on the anonymous github site. Dα (pb ||P0 ) ≤

Details of the real-data ACSIncome illustration

Here we provide the details for the real-data experiment in Section 6, which uses the ACSIncome data from the Folktables benchmark (Ding et al., 2021) available at https://github.com/socialfoundations/folktables, which is released under the MIT license, to give a real-data illustration of the privacy certificates developed above. The experiments were carried out on a Dell laptop featuring an Intel Core i7-11850H CPU @ 2.50GHz, 32 GB of RAM, and an NVIDIA GeForce MX450 GPU (2 GB dedicated VRAM). The experiments can be reproduced with the code provided under https://anonymous.4open.science/r/KSD_Renyi_DP-495A/. The seed is specified in the code. The dataset we use, ACSIncome, a standard benchmark analysed for example in Bullwinkel et al. (2022), is derived from the US Census American Community Survey Public Use Microdata Sample; we use survey year = ”2018”, horizon = ”1 − Year”, and survey = ”person”. Our task is to predict y = 1(an individual’s annual income exceeds $50,000), using demographic and employment variables such as age, education, occupation, marital status, hours worked, sex, and race. The ACS records are public and disclosure-protected, so the experiment is a pseudo-private benchmark. We nevertheless impose a strict public/private/test separation. The 2018 California records form public auxiliary data Dpub ; the 2018 Texas data are 29

Task-aware Kernel Stein certificates for Rényi differential privacy

the pseudo-private training set. One private Texas record is the pair zi = (xi , yi ); adjacency means replacing one such Texas record. Public feature map, model, and task direction Let x contain the ten ACSIncome covariates AGEP, COW, SCHL, MAR, OCCP, POBP, RELP, WKHP, SEX, RAC1P. Using California only, we construct a feature map ϕ(x); we standardize AGEP and WKHP using the means and standard deviations from the California data set alone; we one-hot encode the remaining variables using California-observed categories, and add an intercept. A category which appears only in Texas maps to the all-zero block of the relevant one-hot encoding. To bound o the influence of a single record, we pick a n Bϕ a public constant Bϕ > 0 and threshold ϕB (x) = ϕ(x) min 1, ∥ϕ(x)∥2 . We abbreviate the feature map ϕB by ϕ. A public logistic regression model β0 with a selective ridge penalty is fitted on the public data release Dpub with binary logistic regression negative log-likelihood ℓ(β; (x, y)) = log 1 + exp{ϕ(x)⊤ β} − yϕ(x)⊤ β (39) and ridge matrix Rridge = diag(0, Ip−1 ), so that the intercept is not penalized. The model thus has as overall objective function p−1 n X λX 2 min ℓ(β; zi ) + β . β 2 j=1 j i=1 Each Texas record contributes as private record the fixed gradient g(z) := ∇β ℓ(β0 ; z) = ϕ(x) σ(ϕ(x)⊤ β0 ) − y , where σ(t) = (1 + e−t )−1 . The model β0 , the feature map, and every tuning constant below are fixed before Texas is accessed. Instead of the Fisher information matrix we use a public diagonal matrix; with pi = σ(ϕ(xi )⊤ β0 ) for California records, define X 1 dj = pi (1 − pi )ϕj (xi )2 + λ[Rridge ]jj , |Dpub | i∈Dpub n o and set Ppub,jj = min max(d1j ,dmin ) , Pmax . the diagonal matrix Ppub is public. The use of Pmax is to cap the diagonal entries to prevent rare on-hot coordinates with small entries from generating very large weights. In our first experiment we focus on the output-side task restriction of Section 5. In particular, we do not impose an additional Pufferfish restriction on the protected comparisons. For our public one-dimensional task, let Gpub = {i ∈ Dpub : RAC1Pi = 2}. The category RAC1Pi represents the Recoded Detailed Race Code. It maps an individual’s racial identity to an integer value from 1 to 9 based on the U.S. Census Bureau’s Public Use Microdata Sample (PUMS) categories; RAC1Pi = 2 indicates Black or African American alone. We denote the mean predicted positive-class probability by X 1 hpub (β) = σ(ϕ(xi )⊤ β). (40) |Gpub | i∈Gpub

The subgroup Gpub is used only here to define a public task direction; the resulting certificates should not be interpreted as a race-membership privacy or fairness guarantee. Set bh = ∇hpub (β0 ), ah = Ppub bh , and uh = ah /∥ah ∥2 . The task subspace is S = span{uh } such that US = uh ∈ Rd×1 . Since the model and uh are constructed exclusively from the California data, the task subspace S is public and fixed independently of the Texas data that we view as private. This is in accordance with the task-aware construction of Subsection 5.2. Numerical experiment To illustrate the task-aware mechanism, we use a Gaussian mechanism at α0 = 10, ϵα0 = 1. This fixed mechanism is then evaluated at α ∈ {2, 4, 8, 16}. The experiment uses 20,000 public California and n = 20,000 pseudo-private Texas records used for private training. To obtain the 20,000 records for each state, we use stratified subsampling, without replacement, separately within California and Texas. using the binary income label y as the stratum. We use seed 2026 for California and 2027 for Texas. The privacy guarantee in this experiment treats the already selected 20,000 Texas records as the private dataset. The results thus do not apply to the entire original Texas data, but only to the sample already obtained. The dimension is p = 82; the public parameters are Bϕ = 8, λ = 10−4 , dmin = 10−3 , and Pmax = 25. We decompose each fixed record contribution as g(z) = uh sh (z) + r⊥ (z), with u⊤ h r⊥ (z) = 0, and use California-only thresholds C∥ 30

Task-aware Kernel Stein certificates for Rényi differential privacy

⊤ and C⊥ for the two components, obtained as 99% quantiles of |u⊤ h g(z)| and ||(I − uh uh )g(z)||2 , respectively. For the clipping operator we use the abbreviation clip(t, −c, c) = max{−c; min(t, c)}. The resulting vector release is o 1 Xn YD = uh clip(sh (zi ); C∥ ) + clip2 (r⊥ (zi ); C⊥ ) + σZ, n i q 2 /20000. where Z ∼ N (0, Ip ). The replace-one sensitivity of the full mechanism is bounded by ∆full = 2 C∥2 + C⊥

We now consider its projection on the task subspace S = span(uh ). Since US = uh , the the task-projected privacy output of Subsection 5.2 is US⊤ YD = u⊤ h YD , whose sensitivity is ∆h = 2C∥ /20000. For the same Gaussian noise, 2

εα,h =

C∥ α∆2h = 2 2 εα,full ≤ εα,full . 2 2σ C∥ + C ⊥

(41)

The quantity εα,full is also called the analytic full clipping envelope, and εα,h is the analytic projected clipping envelope. The smaller privacy budget results from evaluating privacy for the projected release u⊤ h YD , rather than from q a stronger guarantee for the full vector-valued release YD . With σ = ∆full

10 2 2 , we set Σ = σ Ip , and use the full

kernel Kfull = σ 2 Ip as well as the projector kernel Kh (x, y) = KB,AdS (x, y) = (ΣUS )(US⊤ ΣUS )−1 (ΣUS )⊤ =σ 2 uh u⊤ h with underlying kernel kB (x, y) ≡ 1 as defined in Subsection 5.3. For a fixed neighbouring pair D ∼ D′ , let δ = E[YD′ ] − E[YD ] denote the corresponding displacement of the means. As kB (x, y) ≡ 1, we have cB,Σ = 1 1 and Theorem 4.3 gives Dαfull = 2α KSD2Kfull . Similarly, Theorem 5.3 gives, for the task-projected release, Dαh = 2 1 2α KSDKh . In particular, α 2 Dαfull = Dαh + 2 ||(I − uh u⊤ h )δ||2 . 2σ Thus, for each neighbouring pair, the difference between the full and task-projected privacy losses is exactly the contribution of the mean shift orthogonal to the public task subspace. This shows that the task-aware KSD exactly certifies the task-aware RDP of the projected mechanism. Figure 1 in the main text, which plots Dαfull and Dαh , shows that the task-aware RDP certificate uses a smaller privacy budget than the standard release; the dashed lines indicate empirical 95% quantiles. The empirical percentiles are not privacy guarantees. Furthermore, we remark that the projected release requires a smaller Rényi privacy budget because the guarantee concerns only the publicly specified task direction; it does not imply the same privacy guarantee for the full vector-valued release. A Pufferfish experiment. The previous experiment illustrated the projected mechanism in which a subspace is private. In this example we pick a discrete Pufferfish example. We protect the recorded sex-race configuration of a target participant i from the Texas dataset; the relevant indicators are Ai = 1(SEXi = 2) (female) and Bi = 1(RAC1Pi = 2). Suppose that the target’s admissible race codes are RAC1P ∈ {1, 2}, where 1 codes for White alone. Thus there are four 01 10 11 ab possible sensitive-attribute configurations for (Ai , Bi ), namely S = {s00 i , si , si , si } with si = {Ai = a, Bi = b}, where (a, b) ∈ C = {(0, 0), (0, 1), (1, 0), (1, 1)}. The prior class assigns arbitrary positive probabilities to the four admissible sex-race completions. We write a record as zi = (wi , ai , bi ), where wi contains all remaining inputs for i used by the mechanism; this includes the income label. The context is the set w = (i, D−i , wi ), where D−i is the set of everybody else’s input. Pufferfish privacy then addresses the question how distinguishable different sex-race configurations of this participant are based on the released statistic, when all other attributes and records are already a′ b′ known. In our experiment we take Q = {(sab ) : (a, b) ̸= (a′ , b′ ).} For the class Θ let w denote everyone else’s i , si ab records and the target’s nonsensitive attributes. Given w there are four ways for completing the dataset; let Dw denote ab the completion with si . Then let ab πab = Pw,π (D = Dw ) P denote a probability distribution on the completions; we assume that πab > 0 for (a, b) ∈ C, and (a,)∈C πab = 1. We take Θ as the set of all such (w, π) pairs. Conditioning on a secret sab i then removes the remaining dataset uncertainty. Again we use the Gaussian mechanism as before; with g(z) = uh sh (z) + r⊥ (z) let ⊤ g̃(z) = uh clip(u⊤ h g(z); C∥ ) + clip2 (g(z) − uh uh g(z); C⊥ ).

The resulting vector release is YD =

1X g̃(zj ) + σZ, n j 31

Task-aware Kernel Stein certificates for Rényi differential privacy

ab where Z ∼ N (0, Ip ). The projected mechanism releases u⊤ h YD . For (a, b) ∈ C set vw = g̃(wi , a, b); then, for a ′ 1 ′ ′ ′ c c protected comparison c = (a, b), c = (a , b ), the mean displacement is δw,c,c′ = n (vw − vw ). With P = Pθ,sci , Q = 2 ′ Pθ,sc , we have for Kfull = σ I that i

KSDKfull (P, Qα|P )2 =

′ α2 c 2 ||v c − vw || , σ 2 n2 w

while for the projector kernel Kh , KSDKh (P, Qα|P )2 =

α2 c′ c 2 [u⊤ h ](vw − vw )] . 2 2 σ n

1 1 and Dαfull = 2α KSD2Kfull while Dαh = 2α KSD2Kh . We highlight that the projected guarantee applies only to the projected release, and the privacy specification is conditional on the declared context rather than a general model of population-level demographic dependence.

In the experiments we also consider changes in sex alone, and changes in race alone. Figure 6 illustrates the results. The clipping envelopes are as in (41). The shorthand arbitrary contexts means that the envelope holds for any context w. The Race-only, Sex-only and Joint comparisons are performed by fixing a context w and varying the specified sensitive attributes. In Race-only comparisons, the target’s sex is held fixed and race is varied, in Sex-only, the target’s race is held fixed and sex is varied; in Joint, sex, race or both may vary. For each comparison type, we report the maximum privacy loss over the contexts evaluated in the experiment. These maxima are finite-class RPP parameters only when the evaluated context list is explicitly declared as the complete context class; otherwise they are diagnostics. More details can be found on the anonymous github site. In Figure 6, for the full vector release, the largest divergences arising from race-only; sex-only changes are comparable over the evaluated context class. In the projected release, race-only comparisons nearly attain the worst-case divergence for joint sex–race protection. Expanding protection from race-only to all joint comparisons adds little to the required worst-case parameter. This figure illustrates that restricting the released output can change the relative importance of different protected comparisons.

Task-aware Kernel Stein certificates for Rényi differential privacy

Conditional sex-race privacy: full release Public clipping envelope: arbitrary contexts joint: Evaluated-context maximum (diagnostic) sex_only: Evaluated-context maximum (diagnostic) race_only: Evaluated-context maximum (diagnostic)

100

10 1

10 2 2

8 10 Renyi order

Conditional sex-race privacy: projected release 10 1

10 2

10 3

Public clipping envelope: arbitrary contexts joint: Evaluated-context maximum (diagnostic) sex_only: Evaluated-context maximum (diagnostic) race_only: Evaluated-context maximum (diagnostic)

8 10 Renyi order

Figure 6: Privacy bounds; top: full release; bottom: projected release. Solid curves show clipping-based upper bounds that are valid for all admissible fixed contexts. Dashed curves show exact maxima of KSD2 /(2α) = Dα over the evaluated contexts and specified secret comparisons.

Task-aware Kernel Stein certificates for Rényi differential privacy

Analyze & explore related research in Conceptio

Related documents