arXiv CSopen access

On the Stability of Spherical Hellinger-Kantorovich Flows and Their Implications for Differential Privacy

On the Stability of Spherical Hellinger-Kantorovich Flows and Their Implications for Differential Privacy Aratrika Mustafi* and Soumya Mukherjee

arXiv:2605.23879v1 [stat.ML] 22 May 2026

Department of Statistics, Pennsylvania State University May 25, 2026

Abstract Gradient-flow sampling interprets a Gibbs distribution as the minimizer of an energy functional over probability measures and generates dynamics converging to this target. Under spherical Hellinger-Kantorovich (SHK) geometry, the flow couples transport and reaction and coincides with birth-death Langevin dynamics. In this work, we develop a perturbation theory for SHK gradient flows. For two potentials V and V ′ we compare the associated flows from a common initialization and quantify how potential discrepancies propagate over time. A uniform perturbation bound yields dimension-free, pointwise control of the log-likelihood ratio and Rényi divergence, while additional structure allows us to derive bounds for the KL divergence as well. We apply these results to approximate sampling for the exponential mechanism in differential privacy. The likelihood-ratio control provides explicit time-dependent Pure-DP guarantees for SHK-based samplers, while the KL bound yields Approximate-DP certificates via hockeystick divergence. We also derive a utility bound separating intrinsic exponential-mechanism suboptimality from finite-time sampling error.

1

Introduction

We consider
the problem of sampling from an unnormalized Boltzmann/ Gibbs density, π(θ) ∝ exp − V (θ) , θ ∈ Θ ⊂ Rd , where the normalization constant is unknown (and/or intractable) and only the potential function V (and typically its derivatives) can be evaluated. This problem arises across various domains in Bayesian inference, statistical physics, and modern machine learning. A common variational perspective on sampling is to characterize the target distribution π as the unique minimizer of a functional (typically a divergence functional) over the space of probability measures. From this viewpoint, sampling can be formulated as evolving an initial distribution ρ0 toward π via the gradient flow of this functional under a suitable geometric structure on the space of probability measures. In this paper, we focus on a gradient flow based sampling methodology built from the spherical Hellinger Kantorovich (SHK), also known as the Wasserstein Fisher Rao (WFR), geometry on the space of probability measures (Kondratyev and Vorotnikov, 2019; Liero et al., 2018; Chizat et al., 2015). When the variational objective is the exclusive KL divergence ρ 7→ KL(ρ∥π), the SHK gradient flow generates a time-indexed family of marginals {ρt }t≥0 (initialized at ρ0 ∈ P2 (Θ) ) that evolves according to the continuity reaction equation (4). This evolution is equivalent to the birth-death Langevin dynamics introduced in Lu et al. (2019) . The SHK geometry should be contrasted with the classical Wasserstein (aka Kantorovich) geometry - In the latter case, 1

the gradient flow is purely transport based and corresponds to the standard continuity equation (Fokker Planck dynamics) (3), whereas the SHK gradient flow augments transport with a reaction component giving rise to a continuity reaction equation which leads to provable acceleration relative to the transport only dynamics in challenging energy landscapes [See Section 3 for more details]. The primary theoretical objective of this work is to quantify the stability of the SHK geometry based sampler under perturbations of the potential. Specifically, given two potentials V and V ′ (and hence two target distributions π ∝ exp(−V ), π ′ ∝ exp(−V ′ )), we study the corresponding SHK flows starting from the same initialization ρ0 , and establish general bounds that control how a perturbation from V to V ′ propagates to the time-marginal densities ρt and ρ′t . In particular, we bound, for every t ≥ 0, different divergences between ρt and ρ′t , thereby providing a rigorous perturbation theory for SHK gradient flow iterates. Next, as an application of this stability theory, we study differential privacy (DP) guarantees for approximate sampling procedures. In DP, a widely used randomized mechanism is the Exponential mechanism, which samples an output θ from a dataset dependent density,
πD (θ) ∝ exp − εLD (θ) (1) where ε > 0 is the privacy parameter that controls the amount of noise injected and LD (θ) is a loss function parametrized by θ. The loss function LD measures how well the parameter θ fits the dataset D, and is typically minimized at estimators that best explain or approximate the data. This is again a Gibbs distribution with potential VD := εLD . For two neighboring datasets D, D′ , privacy hinges on how the law of the released θ changes as VD changes to VD′ . These considerations motivate samplers that (i) operate without access to normalization constants, (ii) admit precise stability guarantees w.r.t perturbations of the potential and (iii) allow these stability guarantees to be translated into DP bounds. The SHK geometry based gradient flow is particularly appealing in this context - it combines transport with a reaction mechanism that reweights probability mass, thereby providing additional flexibility in adapting to changes in the potential. The SHK gradient flow generates a time-indexed family of marginal densities {ρD t }{t≥0} associated with the dataset-dependent potential VD . By leveraging our perturbation bounds for SHK flows, we quantify how ρD t changes when the dataset D is replaced by a neighboring dataset. These stability estimates can then be translated directly into explicit differential privacy guarantees for the time - t distribution generated by the SHK gradient flow when used to approximate πD . Related works The intersection of differential privacy with stochastic optimization and diffusion based sampling is extensive. Foundational treatments of DP and mechanisms based on Gaussian noise, together with practical deployments such as DP-SGD, motivate analyzing privacy loss along stochastic dynamics (Dwork and Roth, 2014; Abadi et al., 2016). For Langevin diffusion and noisy gradient descent, (Chourasia et al., 2021; Altschuler and Talwar, 2022; Ganesh and Talwar, 2020; Ganesh et al., 2022) provide time-dependent privacy guarantees (including Rényi-divergence based analyses) and show how privacy risk can depend delicately on runtime, discretization, and noise structure. A complementary line of work relates privacy loss to information-theoretic quantities such as relative entropy and uses such bounds to control membership-inference and other information-extraction risks (Melis et al., 2019; Mahloujifar et al., 2022; Wibisono et al., 2017). On the analytical side, stability of Fokker-Planck equations and distances between diffusions (and their invariant measures) have been studied through heatkernel bounds, ergodicity theory, and perturbation methods (Mattingly et al., 2002; Pavliotis, 2014; Sanz-Alonso and Stuart, 2016; Bogachev et al., 2014, 2016), often combined with functional inequalities and concentration tools (Bakry et al., 2014; Ledoux, 1999, 2001; Malrieu, 2001; Schlichting, 2019). 2

Closest to our DP-motivated stability viewpoint is the recent work of Borovykh et al. (2023), which derives relative entropy stability bounds for Langevin-type SDEs with possibly anisotropic diffusion and translates them into (ε, δ)-DP and membership inference guarantees; it also discusses privacy-accuracy tradeoffs for anisotropic or matrix-valued noise and related mechanisms. Our work complements this literature by moving beyond transport-only Langevin flows; we analyze the birth-death Langevin dynamics and establish perturbation-based stability bounds tailored to this geometry, which we then specialize to obtain differential privacy guarantees for exponentialmechanism samplers.

2

Notation

Let us denote the collection of probability measures on the domain θ ⊂ Rd as P(Θ) and let P2 (Θ) ⊂ P(Θ) be the subset of probability distributions with finite second moments. Throughout this paper, we use the exclusive version of the KL divergence to
compare an approximating R distribution ρ to a target distribution π i.e. KL(ρ || π) := Θ log πρ dρ. For α ∈ (0, 1) ∪ (1, ∞), R ρ
α−1 1 the Rényi divergence of order α is defined as Dα (ρ || π) = α−1 dρ. To bridge log π our perturbation results to differential privacy guarantees, we also introduce the “Hockey-stick” divergence (Sason and Verdú, 2016; Minasyan and Prabhu, 2018). Let ρ and π be two probability measures on a measurable space {Θ, F}. The Hockey-stick divergence is a parametrized extension of the Total Variation divergence and is defined as Eε (ρ || π) = supS∈F [ρ(S) − exp(ε)π(S)]. We denote the (spatial) gradient operator by ∇, the (spatial) Hessian operator by ∇2 , the divergence operator by ∇· and the Laplacian operator by ∆, where ∆f = ∇ · (∇f ). We denote the collection of real-valued functions defined on the domain [0, T ] × Θ which are k1 -times continuously differentiable in the first argument (for every fixed value of the second argument) and k2 -times continuously differentiable in the second argument (for every fixed value of the first argument) as C k1 ,k2 ([0, T ] × Θ). On any given domain Ω, let C k (Ω) denote the collection of k-times continuously differentiable real-valued functions.

3

Wasserstein gradient flows and spherical Hellinger Kantorovich (SHK) gradient flows

A canonical method for sampling from a density π(θ) ∝ exp(−V (θ)), θ ∈ Θ ⊂ Rd , with unknown normalization constant is the overdamped Langevin diffusion √ dθt = −∇V (θt ) dt + 2dWt (2) which is designed such that π is an invariant distribution of this process and Wt is a d-dimensional Brownian motion. The unadjusted Langevin algorithm (ULA) is obtained by an explicit time discretization of this diffusion and is used in large scale sampling because it only requires knowledge of ∇V . Consequently, if θt has a marginal density ρt then ρt satisfies the Fokker-Planck equation (FPE) ∂t ρt = ∇ · (∇ρt + ρt ∇V ) . (3)   t (θ) Since ∇ · (∇ρt (θ) + ρt (θ)∇V (θ)) = ∇ · ρt (θ)∇ log ρπ(θ) , the above PDE has a variational interpretation originating from the works of Jordan et al. (1998b). Equation (3) can be viewed as the gradient flow (direction of steepest descent) of the KL divergence ρ 7→ KL(ρ∥π) on the space of probability measures endowed with the Wasserstein-2 (W2 ) geometry. 3

While the Wasserstein geometry provides a principled transport based descent mechanism, it is intrinsically mass conserving i.e. the evolution can only reallocate probability mass through advection/diffusion but cannot reweight them. In energy landscapes with well separated modes, this can lead to slow convergence of the KL(ρt ∥π). A natural way to complement this conservative transport is to add a reaction term, which leads to a continuity-reaction of the form, ∂t ρt = ∇ · (∇ρt + ρt ∇V ) − αt ρt ,

(4)

R where αt = log ρt − log π − Θ (log ρt − log π) dρt = log ρt − log π − Eρt (log ρt − log π) (See Lu et al. (2019, Theorem 3.1)). Equation (4) arises from the evolution of the KL functional on the space of probability measures endowed with the spherical Hellinger Kantorovich (aka Wasserstein Fisher Rao) geometry. R The centering Eρt (log ρt − log π) is introduced to ensure that the reaction component satisfies αt ρt = 0, thereby preserving the total mass and guaranteeing ρt remains a probability measure.

4

Main Perturbation based Results

In this Section, we attempt to answer the central analytical question of this paper: How do SHK gradient flows respond to perturbations of the associated potential functions? Our objective is to quantify, in a nonasymptotic manner, how a perturbation in the potential propagates through the transport-reaction dynamics and affects the evolving marginals. Throughout this Section, we impose the following setting. Let Θ ⊂ Rd be a compact domain without boundary. Consider two smooth (C 2 ) potentials V : Θ → R, V ′ : Θ → R. Let us define the corresponding Gibbs target distributions Z exp(−V (θ)) π(θ) = , Z := exp(−V (θ))dθ Z Θ Z exp(−V ′ (θ)) ′ ′ π (θ) = , Z := exp(−V ′ (θ))dθ. Z′ Θ Fix any T > 0. Assume {ρt }0≤t≤T and {ρ′t }0≤t≤T are strictly positive classical solutions ρt , ρ′t ∈ C 1,2 ([0, T ] × Θ),

ρt (θ) > 0, ρ′t (θ) > 0 ∀θ ∈ Θ

to the transport-reaction (birth-death accelerated Langevin) equations

and

∂t ρt = ∇ · (∇ρt + ρt ∇V ) − αt ρt ,

(5)

∂t ρ′t = ∇ · ∇ρ′t + ρ′t ∇V ′ − αt′ ρ′t ,

(6)

respectively, where the (centered) birth-death rates are Z αt (θ) = log ρt (θ) − log π(θ) − (log ρt − log π)dρt Θ

and αt′ (θ) = log ρ′t (θ) − log π ′ (θ) −

Z Θ

4

log ρ′t − log π ′ dρ′t .

By construction, π and π ′ are invariant distributions of (5) and (6), respectively. Further, assume ′ that the density used as the initial   iterate for both flows are the same i.e. ρ0 = ρ0 . Let us define R H(t) := KL(ρt || ρ′t ) = Θ log ρρ′t dρt . t There are several natural ways to measure stability between the perturbed flows, such as pointwise control of the likelihood ratio ρρt′ , integral divergences such as KL or Rényi divergence, or t weaker metrics such as total variation. We begin with the strongest possible control: an L∞ -type bound on the log-likelihood ratio. The complete version of the assumptions required to derive our results from here on are stated in the Appendix in Section A.1. Theorem 1. Let π ∝ exp(−V ) and π ′ ∝ exp(−V ′ ) be Gibbs/Boltzmann corresponding to the potentials V and V ′ . Fix initial densities ρ0 = ρ′0 on Θ which are strictly positive, and smooth enough so that the SHK Fokker Planck Equations 5 and (6) have positive classical solutions ρt , and ρ′t , respectively, for all t ≥ 0. Define s0 (θ) := log

ρ0 (θ) , π(θ)

s′0 (θ) := log

and

R0′ := max s′0 (θ) − min s′0 (θ).

R0 := max s0 (θ) − min s0 (θ), θ∈Θ

ρ0 (θ) π ′ (θ)

θ∈Θ

θ∈Θ

θ∈Θ

If Assumption (A1) holds, i.e. ∥V − V ′ ∥∞ ≤ ∆pot , then for every t ≥ 0 and every θ ∈ Θ, log

ρt (θ) ≤ 2∆pot + exp(−t)(R0 + R0′ ) ρ′t (θ)

and for every α > 1, the α-Rényi divergence satisfies Dα (ρt || ρ′t ) ≤ 2∆pot + exp(−t)(R0 + R0′ ). If instead Assumption (A1′ ) holds i.e. supθ∈Θ (V (θ) − V ′ (θ)) − inf θ∈Θ (V (θ) − V ′ (θ)) ≤ ∆pot,osc , then we have that, for every t ≥ 0 and every θ ∈ Θ, log

ρt (θ) ≤ ∆pot,osc + exp(−t)(R0 + R0′ ) ρ′t (θ)

and for every α > 1, the α-Rényi divergence satisfies Dα (ρt || ρ′t ) ≤ ∆pot,osc + exp(−t)(R0 + R0′ ). The proof is available in Section A.2.1 of the Appendix. Remark 1. Theorem1 gives a pointwise stability bound for the SHK gradient flow under a uniform perturbation of the potential (Assumption (A1) or Assumption (A1′ )). The estimate cleanly decomposes into: (i) a model/target mismatch term of order ∆pot /∆pot,osc , and (ii) an initialization term that decays like e−t through the oscillations R0 , R0′ of the initial log-densities relative to the respective Gibbs targets. This makes the role of the reaction component explicit: it exponentially ′ damps the spatial oscillation of st = log(ρt /π) (and similarly for st ), which is precisely what yields the e−t factor. A useful viewpoint of this result, is that the bound is dimension-free and does not invoke any convexity, spectral gap, or log-Sobolev structure. In particular, it provides an L∞ -type control on ′ the density ratio ρt /ρt , which is stronger than controlling an integral divergence (KL/Rényi) alone, and can therefore be directly translated into uniform stability statements. 5

Remark 2. As t → ∞, the transient term vanishes and the bound saturates at a constant of order ∆pot /∆pot,osc (coming from the intrinsic discrepancy between π and π ′ ). This term is unavoidable, unless the two target distributions coincide. In Theorem 1, we are able to prove, under very mild assumptions on the initializations of ′ ′ the SHK gradient flow  iterates ρ0 and ρ0 corresponding to the potentials V and V , that the log-

likelihood ratio log ρρt′ between the two perturbed flows {ρt }t≥0 and {ρ′t }t≥0 remain bounded for t any t, and the bound improves as the flow progresses towards t → ∞. Based on this log-likelihood bound, we are also able to derive a bound on the Rényi divergence of orders α > 1 between ρt and ρ′t for any t ≥ 0. However, the analysis used for Theorem 1 does not extend to the limiting α → 1 scenario, if our goal is to bound the (exclusive) KL divergence between ρt and ρ′t . To this end, we now proceed to bound the (exclusive) KL divergence between ρt and ρ′t . In Theorem 1, we derived the log-likelihood and Rényi divergence bounds under Assumption (A1), which bounds the size of perturbation of the potentials in the sense that ∥V − V ′ ∥∞ ≤ ∆pot , or alternatively under Assumption (A1′ ), which controls the oscillation of the potential sensitivity using the bound supθ∈Θ (V (θ) − V ′ (θ)) − inf θ∈Θ (V (θ) − V ′ (θ)) ≤ ∆pot,osc . In order to derive the bound on KL(ρt || ρ′t ) and ρ′t , we have to rely on an additional assumption involving control of the size of perturbation of the gradients of the potentials i.e. ∥∇V − ∇V ′ ∥∞ ≤ ∆gradpot . However, that leads to a bound on KL(ρt || ρ′t ) which grows atleast linearly in t, and hence represents uncontrolled divergence between the two perturbed flows. We have derived this result as Theorem 6, which has been presented in Section A.2.2 of the Appendix. Upon further exploration, it was observed that some additional structural assumptions regarding only the target distributions π and π ′ (Log-Sobolev conditions), which are quite standard in the literature, it is possible to derive a bound on KL(ρt || ρ′t ) that remains bounded and controlled for any time t ≥ 0 and stabilizes within a short period from initialization. Theorem 2 provides the derived bound. Theorem 2. Assume that we fix a common initial density ρ0 on Θ such that {ρt }t≥0 , {ρ′t }t≥0 ∈ C 1,2 ([0, T ] × Θ) are strictly positive solutions of the transport-reaction equations (5) and (6) on [0, T ]. Further, let Assumption (A2) hold true for the potential functions V and V ′ . Finally, let π and π ′ satisfy Assumption (A3). Further, assume that R0 , R0′ ≤ B for some universal constant B ≥ 0, where ρ  ρ  t t Rt := max log (θ) − min log (θ), θ∈Θ θ∈Θ π π  ′  ′ ρ ρ Rt′ := max log t′ (θ) − min log t′ (θ) θ∈Θ θ∈Θ π π and let Star be a constant such that log ππ(θ) ′ (θ) ≤ Star for all θ ∈ Θ. Then, for all t ≥ 0 and any 0 < c < 1, H ′ (t) :=

d KL(ρt || ρ′t ) dt

≤ − 2(1 − c)e−e

−t B

λGibbs H(t) +

1 2 (R′ )2 1 ∆gradpot + 0 e−2t + Star R0 e−t + 2R0′ e−t . 4c 16 2

Consequently, we have that H(t) = KL(ρt || ρ′t )   Z t Z t −e−u B ≤ exp −2(1 − c)λGibbs e du bc (s) ds, 0

s

6

(R′ )2

1 where bc (t) = 4c ∆2gradpot + 160 exp(−2t) + 12 Star R0 e−t + 2R0′ exp(−t). Further, as a corollary, the following explicit result holds. Let RD , RD′ ≤ B for some B ≥ 0 independent of the datasets D and D′ . Define   ∆2gradpot Star B2 A1 := , A2 := B + 2 , A3 := , κ := 2(1 − c)e−B λGibbs . 4c 2 16

Then for all t ≥ 0, we have that  e−t − e−κt 1 − e−κt   + A if κ = ̸ 1, 2 : A  2 1   κ κ−1   −2t − e−κt   e   + A3   κ−2   −κt  1−e  −t if κ = 1 : A1 + A2 te H(t) ≤ κ   e−2t − e−κt    + A 3   κ−2    1 − e−κt e−t − e−κt   if κ = 2 : A1 + A2   κ κ−1    + A3 te−2t

.

Under Assumption (A1), the choice Star = 2∆pot holds, while the choice Star = ∆pot,osc is valid under Assumption (A1′ ). The proof of Theorem 2 is available in Section A.2.3 of the Appendix. Remark 3. Theorem 2 refines Theorem 6 by exploiting the log-Sobolev structure of the targets (Assumption (A3)) to introduce an explicit negative drift term in the KL dynamicsH ′ (t) ≤ −c(t) H(t) + bc (t). Here, c(t) = 2(1 − c) exp(−e−t B)λGibbs arises by lower bounding the Fisher information I(t) in terms of H(t) through LSI, while accounting for the time-dependent Holley-Strook degradation induced by the oscillation bound Rt ≤ e−t B. This is the main mechanism turning the stability estimate from potentially growing (as in Theorem6) into uniformly controlled over time. The factor exp(−e−t B) captures that the effective LSI constant along the flow and it improves with time as the oscillation of log(ρt /π) shrinks. At t = 0 this factor is exp(−B), while as t → ∞ it tends to 1- thus the contractivity strengthens over time. The explicit bound implies H(t) −−−→ t→∞

A1 κ

(up to some vanishing terms),

so the KL divergence remains bounded for all t under LSI. In particular, the long-time plateau is controlled by the balance between the forcing size A1 ∝ ∆2gradpot and the contractivity rate κ ∝ λGibbs . When ∆gradpot = 0, the forcing size disappears (A1 = 0) and the bound predicts H(t) → 0, i.e., asymptotic coincidence of the two flows started from the same initialization.

5

Application to Differential Privacy

In this section, we try to apply the previous results in differential privacy. Differential privacy formalizes privacy as a distributional notion of stability for randomized mechanisms operating 7

on different datasets. A mechanism is said to be differentially private if its output measures corresponding to neighboring datasets remain uniformly close. This ensures that no single data point can significantly influence the released distribution. Two datasets D and D′ are called neighboring if they differ in the data of at most one individual. Definition 1 (Approximate and Pure Differential Privacy). (Dwork and Roth, 2014) Let D be the dataset space with a symmetric neighboring/adjacency relation D ∼ D′ . A randomized mechanism M with outputs in Θ is (ε, δ)-DP if for all neighboring datasets D and D′ and all measurable sets S ⊆ Θ,

P(M (D) ∈ S) ≤ exp(ε)P M D′ ∈ S + δ. If the randomized algorithm M satisfies (ε, δ)-DP with δ = 0, it is said to satisfy ε-Pure DP. Theorem 3 (Pure DP guarantees under sensitivity bound on potentials). Let D and D′ be neighboring datasets, with potentials VD , VD′ corresponding to Exponential mechanism densities D′ πD ∝ exp(−VD ) and πD′ ∝ exp(−VD′ ). Fix initial densities ρD 0 and ρ0 on Θ that are independent of the dataset, strictly positive, and smooth enough so that the SHK Fokker Planck Equations 5 and D′ (6) have positive classical solutions ρD t , and ρt , respectively, for all t ≥ 0. Define sData (θ) := log 0 and

ρData (θ) 0 , πData (θ)

RData := max sData (θ) − min sData (θ) 0 0 θ∈Θ

θ∈Θ

for Data ∈ {D, D′ }. Then, if RD , RD′ ≤ B for some B ≥ 0 independent of the datasets D and D′ , and if the potentials VD and VD′ satisfy Assumption (A1) i.e. ∥VD − VD′ ∥∞ ≤ ∆pot , then the mechanism Mt (D) that outputs θt ∼ ρD t is (ε1 (t), 0)-DP (i.e. satisfies ε1 (t)-Pure DP) with ε1 (t) = 2∆pot + 2B exp(−t). If instead the potentials VD and VD′ satisfy Assumption (A1′ ) i.e. supθ∈Θ (VD (θ) − VD′ (θ)) − inf θ∈Θ (VD (θ) − VD′ (θ)) ≤ ∆pot,osc , then the mechanism Mt (D) that outputs θt ∼ ρD t is (ε2 (t), 0)DP (i.e. satisfies ε2 (t)-Pure DP) with ε2 (t) = ∆pot,osc + 2B exp(−t). The proof of Theorem 3 is available in section A.2.4 in the Appendix. Remark 4. Theorem 3 is an immediate (and sharp in spirit) privacy corollary of the pointwise control in Theorem 1. The key point is that pure DP is governed by uniform likelihood-ratio bounds, ε(t) ρD′ (θ) for all θ. Theorem 3 shows that, provided the i.e. inequalities of the form ρD t (θ) ≤ e t initialization is dataset-independent and the initial log-density mismatch is uniformly bounded (RD , RD′ ≤ B for some B ≥ 0), the SHK flow inherits a pure-DP guarantee with an explicit time profile ε(t) with ε(t) = ε1 (t) under Assumption (A1) and ε(t) = ε2 (t) under Assumption (A1′ ), respectively. Remark 5. The ε(t) term consists of: (i) a dataset sensitivity term 2∆pot or ∆pot,osc (the inherent stability scale of the exponential-mechanism targets under Assumption (A1) or Assumption (A1′ ), respectively), together with (ii) an exponentially decaying transient term 2B exp(−t) stemming only from initialization. Thus, the price of not starting at stationarity manifests as an additive, 8

time-vanishing privacy overhead. As t → ∞, ε(t) = ε1 (t) → 2∆pot under Assumption (A2) and ε(t) = ε2 (t) → ∆pot,osc under Assumption (A1′ ). In other words, once the transient term vanishes, the sampler’s pure-DP level matches (up to this sensitivity constant) the irreducible privacy level dictated by how different the neighboring Gibbs targets can be under Assumption (A1) or (A1′ ). Running the sampler longer cannot improve the pure-DP constant below this level, since even exact samples from πD and πD′ can differ by that amount in worst-case likelihood ratio. Next we show that under stronger assumptions, such as the LSI conditions for the Exponential mechanism, we have the following result. Theorem 4 (Approximate DP guarantees n under o LSI condition). Assume that we fix a common  D ′ D initial density ρ0 on Θ such that ρt t≥0 , ρt ∈ C 1,2 ([0, T ] × Θ) are strictly positive solutions t≥0

of the transport-reaction equations (5) and (6) on [0, T ]. Further, let Assumption (A2) hold true for the potential functions let πD and πD′ satisfy Assumption (A3). Define  DataVD and VD′ . Finally,  Data ρ0 ρ0 D,D′ RData := maxθ∈Θ log π (θ) − minθ∈Θ log π (θ) for Data ∈ {D, D′ } and let Star be a Data

Data

′

D,D for all θ ∈ Θ. constant such that log ππD′(θ) (θ) ≤ Star D

Further, assume that RD , RD′ ≤ B for some B ≥ 0 independent of the datasets D and D′ . Define ! D,D′ ∆2gradpot Star B2 , A2 := B + 2 , A3 := , κ := 2(1 − c) exp(−B)λGibbs . A1 := 4c 2 16 Then, for all t ≥ 0 and any 0 < c < 1, we can choose any ε > 0 such that the mechanism Mt (D) that outputs θt ∼ ρD t is (ε, δt )-DP (i.e. satisfies (ε, δt ) Approximate-DP) with δt = where,

H̄(t) . ε

 e−t − e−κt 1 − e−κt   + A if κ = ̸ 1, 2 : A  2 1   κ κ−1   −2t − e−κt   e   + A3   κ−2   −κt  1−e  −t if κ = 1 : A1 + A2 te H̄(t) = κ   e−2t − e−κt    + A 3   κ−2    1 − e−κt e−t − e−κt   if κ = 2 : A1 + A2   κ κ−1    + A3 te−2t ′

.

′

D,D D,D Under Assumption (A1), the choice Star = 2∆pot holds, while the choice Star = ∆pot,osc is valid ′ under Assumption (A1 ).

The detailed proof is provided in section A.2.4 of the Appendix. Remark 6. Theorem 4 moves beyond pure DP by leveraging a KL-based route to (ε, δ)-DP. D′ Concretely, it combines - (i) a non-asymptotic bound on H(t) = KL(ρD t ∥ρt )(derived from Theorem 2), and (ii) the standard inequality relating hockey-stick divergence to KL,which yields (ε, δ)-DP with δ proportional to H(t) ε . The explicit upper bound H̄(t) reveals three distinct contributions: 9

• A1 captures the effect of gradient sensitivity ∆gradpot and comes from the drift mismatch term; it is the only term that does not come with an explicit e−t or e−2t prefactor. • A2 and A3 encode transient contributions driven by the potential sensitivity ∆pot /∆pot,osc and the initialization oscillation bound B; these terms decay at rates e−t and e−2t (depending on κ). • The parameter c ∈ (0, 1) is a tuning knob originating from Young’s inequality: decreasing c strengthens the contraction rate κ (through 1 − c) but increases A1 = ∆2gradpot /(4c). Hence, c mediates an explicit tradeoff between contractivity and the size of the forcing term. Remark 7. For any κ > 0, the transient terms vanish and H̄(t) −−−→ t→∞

A1 κ

and therefore

δt =

H̄(t) A1 −−−→ . ε t→∞ κ ε

Thus, the approximate-DP guarantee saturates to a nonzero plateau whenever ∆gradpot > 0. Intuitively, as the sampler runs longer it becomes more dataset-dependent, until the stability is limited by the balance between (i) the contractive effect induced by the LSI and (ii) the persistent forcing due to the drift perturbation. In the special case ∆gradpot = 0 (no drift mismatch), one has A1 = 0 and the bound predicts δt → 0, and we approach pure-DP guarantees in the long-time regime.

5.1

Utility analysis

We now proceed to analyze the utility of the marginal densities {ρt }t≥0 generated by the SHK based sampler. In the standard setting when the Exponential mechanism, introduced by McSherry and Talwar (2007), is typically used, the goal is to obtain values θ ∈ Θ which are sufficiently close to being minimizers of the the objective function of interest, say f : Θ → R, which is any measurable function bounded below. Letf∗ := inf θ∈Θ f (θ). Choosing any β > 0, the exponential-mechanism target density is constructed as Z exp(−βf (θ)) πβ (θ) := , Zβ := exp(−βf (θ))dθ. Zβ Θ In the most common scenarios, the function f depends on sensitive/confidential information D, which is typically a dataset belonging to a dataset space D. The standard practice in Differential ε Privacy is to choose β ∝ ∆ where ∆ is a measure of how sensitive the function f is to perturbation of the dataset. For example, a dataset could be a sample of n i.i.d individuals from a population, and the sensitivity ∆ of the function f characterizes the amount of perturbation of the function when a single individual’s data is changed, creating “neighboring” datasets. Lower β will lead to more uniformly distributed mechanisms, leading to better privacy guarantees. For ease of presentation, we will ignore the implications of the choice of β in this work, and focus on the utility analysis. In order to proceed with the analysis, let us define the volume of a near-optimal sublevel set. For any α > 0, define Sα := {x ∈ Θ : f (x) ≤ f∗ + α}, mα := Vol(Sα ) and m := Vol(Θ), where all volumes are with respect to the Lebesgue measure. We first characterize how close is the expected value of the objective function f under the exponential mechanism to the true minimum of the function f . Proposition 1 (Expected suboptimality of the exponential mechanism). Assume 0 < mα ≤ m < ∞. Then   1 m Eπβ [f ] − f∗ ≤ α + log +1 . β mα 10

Let ρt be the law of the output of the SHK gradient flow based sampler at time t. The goal is to control Eρt [f ] − f∗ . We characterize the closeness of the expected value of the objective function f under the law ρt at time t to the true minimum of the function f in the following theorem. Theorem 5 (Utility bound for SHK gradient flow sampler). Let Θ be a compact domain with volume m. Let f : Θ → R be measurable, bounded, and bounded below, with f∗ = inf Θ f . Fix β > 0 and let πβ ∝ exp(−βf ) be the density of the exponential mechanism. Let ρt be the marginal density of the WFR/SHK sampler targeting πβ at time t constructed by choosing the potential function V = βf . Assume there exists a time t0 such that H (t0 ) := KL (ρt0 ∥πβ ) ≤ 1 and ρt (θ) inf 0 ≥ exp(−M ) θ∈Θ πβ (θ) 1 for some M ≥ 1. Fix δ ∈ (0, 1/4) and define t∗ = t0 + log(M/δ) + 1−2δ log(1/δ). Then for every t ≥ t∗ and every α > 0 with mα := Vol (Sα ) > 0, we have that r     1 m 1 2 − 3δ Eρt [f ] − f∗ ≤ α + + 1 + 2∥f ∥∞ H (t0 ) exp − (t − t∗ ) . log β mα 2 2

The proofs of Proposition 1 and Theorem 5 are available in Section A.2.6 and Section A.2.6 of the Appendix, respectively.

6

Conclusion

This work analyzes the sensitivity of SHK/WFR gradient-flow samplers, equivalently, birth-death accelerated Langevin dynamics, and relates it to perturbations of the underlying potential. The central contribution is a nonasymptotic perturbation bound for the time-marginal laws generated by two SHK flows driven by V and V ′ , started from the same initial density. Then, these stability statements are translated directly into differential privacy guarantees for exponential-mechanism sampling, which has practical applications in diverse domains. Existing papers on SHK gradient flows such as Lu et al. (2019) already convincingly establish the advantages of the additional flexibility and acceleration gained due to the reaction term in comparison to Kantorovich (Wasserstein) transport-based Langevin dynamics. We perform some toy numerical experiments to test the validity of our perturbation bounds and empirically demonstrate the stability of perturbed SHK flows in Section A.3 of the Appendix. As a natural extension to this work, one can try to relax the assumptions that we make and also develop Rényi-DP or f -DP based guarantees for SHK gradient flow based samplers.

References Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308–318, 2016. Jason Altschuler and Kunal Talwar. Privacy of noisy stochastic gradient descent: More iterations without more privacy loss. Advances in Neural Information Processing Systems, 35:3788–3800, 2022.

11

Dominique Bakry, Ivan Gentil, and Michel Ledoux. Symmetric Markov Diffusion Operators, page 119–174. Springer International Publishing, 2014. ISBN 9783319002279. doi: 10.1007/ 978-3-319-00227-9_3. URL http://dx.doi.org/10.1007/978-3-319-00227-9_3. Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsampling: Tight analyses via couplings and divergences. Advances in neural information processing systems, 31, 2018. V.I. Bogachev, M. Röckner, and S.V. Shaposhnikov. Distances between transition probabilities of diffusions and applications to nonlinear fokker–planck–kolmogorov equations. Journal of Functional Analysis, 271(5):1262–1300, 2016. ISSN 0022-1236. doi: https://doi.org/10.1016/j.jfa.2016.05.016. URL https://www.sciencedirect.com/science/article/pii/S0022123616301239. Vladimir Igorevich Bogachev, Andrei Igorevich Kirillov, and Stanislav Valer’evich Shaposhnikov. The kantorovich and variation distances between invariant measures of diffusions and nonlinear stationary fokker-planck-kolmogorov equations. Mathematical Notes, 96(5):855–863, 2014. Anastasia Borovykh, Nikolas Kantas, Panos Parpas, and Greg Pavliotis. Privacy risk for anisotropic langevin dynamics using relative entropy bounds. arXiv preprint arXiv:2302.00766, 2023. Lenaic Chizat, Bernhard Schmitzer, Gabriel Peyré, and François-Xavier Vialard. An interpolating distance between optimal transport and fisher-rao. arXiv preprint arXiv:1506.06430, 2015. Rishav Chourasia, Jiayuan Ye, and Reza Shokri. Differential privacy dynamics of langevin diffusion and noisy gradient descent. Advances in Neural Information Processing Systems, 34:14771–14781, 2021. Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and trends® in theoretical computer science, 9(3-4):211–487, 2014. Arun Ganesh and Kunal Talwar. Faster differentially private samplers via rényi divergence analysis of discretized langevin mcmc. Advances in Neural Information Processing Systems, 33:7222–7233, 2020. Arun Ganesh, Abhradeep Thakurta, and Jalaj Upadhyay. Differentially private sampling from rashomon sets, and the universality of langevin diffusion for convex optimization. arXiv preprint arXiv:2204.01585, 2022. Richard Holley and Daniel W Stroock. Logarithmic sobolev inequalities and stochastic ising models. 1986. Richard Jordan, David Kinderlehrer, and Felix Otto. The variational formulation of the fokker– planck equation. SIAM Journal on Mathematical Analysis, 29(1):1–17, 1998a. doi: 10.1137/ S0036141096303359. URL https://doi.org/10.1137/S0036141096303359. Richard Jordan, David Kinderlehrer, and Felix Otto. The variational formulation of the fokker– planck equation. SIAM journal on mathematical analysis, 29(1):1–17, 1998b. Stanislav Kondratyev and Dmitry Vorotnikov. Spherical hellinger–kantorovich gradient flows. SIAM Journal on Mathematical Analysis, 51(3):2053–2084, 2019. M. Ledoux. Logarithmic Sobolev Inequalities for Unbounded Spin Systems Revisited, page 167–194. Springer Berlin Heidelberg, 2001. ISBN 9783540446712. doi: 10.1007/978-3-540-44671-2_13. URL http://dx.doi.org/10.1007/978-3-540-44671-2_13. 12

Michel Ledoux. Concentration of measure and logarithmic Sobolev inequalities, page 120–216. Springer Berlin Heidelberg, 1999. ISBN 9783540484073. doi: 10.1007/bfb0096511. URL http://dx.doi.org/10.1007/bfb0096511. Matthias Liero, Alexander Mielke, and Giuseppe Savaré. Optimal entropy-transport problems and a new hellinger–kantorovich distance between positive measures. Inventiones mathematicae, 211 (3):969–1117, 2018. Yulong Lu, Jianfeng Lu, and James Nolen. Accelerating langevin sampling with birth-death. arXiv preprint arXiv:1905.09863, 2019. Saeed Mahloujifar, Alexandre Sablayrolles, Graham Cormode, and Somesh Jha. Optimal membership inference bounds for adaptive composition of sampled gaussian mechanisms. arXiv preprint arXiv:2204.06106, 2022. F. Malrieu. Logarithmic sobolev inequalities for some nonlinear pde’s. Stochastic Processes and their Applications, 95(1):109–132, September 2001. ISSN 0304-4149. doi: 10.1016/s0304-4149(01) 00095-3. URL http://dx.doi.org/10.1016/s0304-4149(01)00095-3. J.C. Mattingly, A.M. Stuart, and D.J. Higham. Ergodicity for sdes and approximations: locally lipschitz vector fields and degenerate noise. Stochastic Processes and their Applications, 101(2): 185–232, 2002. ISSN 0304-4149. doi: https://doi.org/10.1016/S0304-4149(02)00150-3. URL https://www.sciencedirect.com/science/article/pii/S0304414902001503. Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07), pages 94–103, 2007. doi: 10.1109/FOCS.2007.66. Luca Melis, Congzheng Song, Emiliano De Cristofaro, and Vitaly Shmatikov. Exploiting unintended feature leakage in collaborative learning. In 2019 IEEE symposium on security and privacy (SP), pages 691–706. IEEE, 2019. Edgar Minasyan and Vinay Prabhu. Hockey-stick gan. 2018. Grigorios A Pavliotis. Stochastic processes and applications. Texts in applied mathematics, 60: 41–43, 2014. Daniel Sanz-Alonso and Andrew M Stuart. Gaussian approximations of small noise diffusions in kullback-leibler divergence. arXiv preprint arXiv:1605.05878, 2016. Igal Sason and Sergio Verdú. f -divergence inequalities. IEEE Transactions on Information Theory, 62(11):5973–6006, 2016. André Schlichting. Poincaré and log–sobolev inequalities for mixtures. Entropy, 21(1):89, 2019. Lezhi Tan and Jianfeng Lu. Accelerate langevin sampling with birth-death process and exploration component. SIAM/ASA Journal on Uncertainty Quantification, 13(3):1265–1293, 2025. Andre Wibisono, Varun Jog, and Po-Ling Loh. Information and estimation in fokker-planck channels. In 2017 IEEE International Symposium on Information Theory (ISIT), pages 2673–2677. IEEE, 2017.

13

A

Technical appendices and supplementary material

A.1

Assumptions on the potential function

Assumption (A1) (Bound on size of perturbation of potentials). Let the potentials V and V ′ satisfy a uniform pointwise sensitivity bound: V − V ′ ∞ := sup V (θ) − V ′ (θ) ≤ ∆pot . θ∈Θ

Assumption (A1′ ) (Alternative bound on size of perturbation of potentials). Let the potentials V and V ′ satisfy a uniform oscillation sensitivity bound:

sup V (θ) − V ′ (θ) − inf V (θ) − V ′ (θ) ≤ ∆pot,osc . θ∈Θ

θ∈Θ

Assumption (A2) (Bound on size of perturbation of gradient of potentials). Let the gradients of the potentials V and V ′ satisfy a uniform pointwise sensitivity bound: ∇V − ∇V ′ ∞ := sup ∇V (θ) − ∇V ′ (θ) ≤ ∆gradpot . θ∈Θ

Assumption (A3) (Log Sobolev Inequality (LSI) for target Gibbs densities). Let π ∝ exp(−V ) ′ and π ′ ∝ exp(−V inequality with the same constant λGibbs > 0 i.e. for all R 2) satisfy a log-Sobolev R smooth f with f dπ = 1 and f 2 dπ ′ = 1, it holds that Z Z Z Z

2 2 2 2 2 2 2 2 2 ′ Entπ f := f log f dπ ≤ ∥∇f ∥ dπ, and Entπ′ f := f log f dπ ≤ ∥∇f ∥2 dπ ′ . λGibbs λGibbs Remark 8. The potentials V and V ′ are only defined up to additive constants. Replacing +c)] exp(−c)×exp(−V ) R V by V + c does not change the Gibbs density π since R exp[−(V = exp(−c)× = exp[−(V +c)] exp(−V ) Θ

Θ

R exp(−V ) . The transport term in the SHK dynamics (Equation 4) also remains invariant since Θ exp(−V ) ∇(V + c) = ∇V . The reaction term is also unchanged since it depends on log πρ , and π is unchanged. Therefore the quantity ∥V − V ′ ∥∞ is not intrinsic: it changes if one adds a constant to V or V ′ . The intrinsic quantity is instead inf c∈R ∥V − V ′ − c∥∞ , which can be exactly expressed as 1 ′ ′ 2 [supθ∈Θ (V (θ) − V (θ)) − inf θ∈Θ (V (θ) − V (θ))]. Consequently, considering a uniform oscillation sensitivity bound of the form considered in Assumption (A1′ ) may be more natural.

Remark 9. Assumption (A3) postulates that the two Gibbs targets π ∝ exp(−V ) and π ′ ∝ exp(−V ′ ) satisfy a log-Sobolev inequality with a common constant λGibbs > 0. In the differential privacy application (where VD = εpriv LD is the exponential-mechanism potential associated with dataset D), it is often reasonable to treat λGibbs as uniform over neighboring datasets (or even over all datasets in a class), for several standard reasons: • Uniform strong log-concavity / curvature control- If there exists m > 0, independent of D, such that ∇2 VD (θ) ⪰ mId for all θ ∈ Θ and all datasets D, then each πD satisfies an LSI with constant at least m (e.g., by Bakry-Émery-type criteria). In exponential-mechanism settings, such uniform curvature is commonly P enforced by adding a dataset independent strongly convex regularizer (e.g., LD (θ) = n1 i ℓ(θ; xi ) + µ2 ∥θ∥2 ), in which case m is governed by the regularization strength and scales linearly with the privacy parameter εpriv through VD = εpriv LD . 14

• Stability of LSI under bounded perturbations (Holley-Strook - Lemma 14) - More generally, suppose a reference Gibbs measure π̄ ∝ exp(−V̄ ) satisfies an LSI with constant λ̄ > 0, and each dataset-dependent potential decomposes as VD = V̄ + ψD with uniformly bounded oscillation osc(ψD ) = sup ψD − inf ψD ≤ C (independent of D). Then the Lemma 14 implies that πD satisfies an LSI with constant at least exp(−C)λ̄. In particular, for neighboring datasets D ∼ D′ , Assumption (A1) gives the uniform bound osc(VD − VD′ ) ≤ 2∆pot while Assumption (A1′ ) directly gives the bound osc(VD − VD′ ) ≤ ∆pot,osc , so LSI constants for πD and πD′ are comparable up to a multiplicative factor depending only on ∆pot /∆pot,osc . Thus, it is natural to work with a common constant chosen as a uniform lower bound over the dataset class. • Compactness and dataset-independent regularity bounds - When Θ is compact (as assumed throughout) and the family of potentials {VD }D satisfies dataset-uniform regularity/oscillation bounds, one can often obtain a strictly positive LSI constant that depends only on these uniform bounds and the geometry of Θ (and hence can be taken independent of D) Finally, we stress that Assumption (A3) is only used to obtain contractive control of KL (via Fisher information) in Theorems 2, 6 and 4. The pointwise perturbation bound in Theorem 1, and the resulting pure DP guarantee in Theorem 3, do not rely on any LSI assumption.

A.2

Proof of theorems

A.2.1

Proof of Theorem 1

Proof. Fix t ≥ 0 and θ ∈ Θ. Then, we have that ρt (θ) = π(θ)ut (θ),

ρ′t (θ) = π ′ (θ)u′t (θ),

ρ′

where ut = ρπt , u′t = πt′ . Then log

ρt (θ) ut (θ) π(θ) + log ′ = log ′ . ρ′t (θ) π (θ) ut (θ)

Taking absolute values and using triangle inequality, we have that log

π(θ) π(θ) ρt (θ) + log ut (θ) − log u′t (θ) ≤ log ′ + |log ut (θ)| + log u′t (θ) . ≤ log ′ ρ′t (θ) π (θ) π (θ)

Using Proposition 2, we have that |log ut (θ)| ≤ exp(−t)R0 and |log u′t (θ)| ≤ exp(−t)R0′ . Let Star be any constant such that π(θ) ≤ Star for all θ ∈ Θ. log ′ π (θ) Combining, we have that log

π(θ) ρt (θ) ≤ log ′ + |log ut (θ)| + log u′t (θ) ′ ρt (θ) π (θ) ≤ Star + exp(−t)(R0 + R0′ ).

(7)

Under Assumption (A1), Lemma 9 gives Star = 2∆pot . Under Assumption (A1′ ), Lemma 10 gives Star = ∆pot,osc . This proves the two pointwise bounds. Also, whenever ρt (θ) log ′ ≤ Star + exp(−t)(R0 + R0′ ), ρt (θ) 15

we have

Z  α−1 ρt 1 dρt log α−1 ρ′t Z  
1 ≤ exp [α − 1] Star + exp(−t)(R0 + R0′ ) dρt log α−1 Θ =Star + exp(−t)(R0 + R0′ ).

Dα (ρt || ρ′t ) =

Applying the two choices of Star above completes the proof.

A.2.2

Bound on KL divergence between perturbed flows under L∞ control of potentials and their gradients

Theorem 6. Assume that we fix a common initial density ρ0 on Θ such that {ρt }t≥0 , {ρ′t }t≥0 ∈ C 1,2 ([0, T ] × Θ) are strictly positive solutions of the transport-reaction equations (5) and (6) on [0, T ]. Finally, let Assumption (A2) hold true for the potential functions V and V ′ and let Star be a constant such that log ππ(θ) ′ (θ) ≤ Star for all θ ∈ Θ. Then, for all t ≥ 0, H ′ (t) :=

d (R′ )2 1 1 KL(ρt || ρ′t ) ≤ ∆2gradpot + 0 exp(−2t) + Star R0 exp(−t) + 2R0′ exp(−t) dt 4 16 2

where Rt := max log θ∈Θ

ρ  t

π

(θ) − min log θ∈Θ

ρ  t

π

(θ),

Rt′ := max log θ∈Θ

 ′  ′ ρt ρt (θ) − min log (θ). ′ θ∈Θ π π′

Then for all t ≥ 0, 1 (R′ )2 H(t) ≤ ∆2gradpot t + 0 (1 − exp(−2t)) + 4 32



 Star R0 ′ + 2R0 (1 − exp(−t)). 2

Under Assumption (A1), the choice Star = 2∆pot holds, while the choice Star = ∆pot,osc is valid under Assumption (A1′ ). Proof. Under the given conditions, Proposition 3 gives that d KL(ρt || ρ′t ) dt   2   Z Z
ρt ρt ′ dρt + ∇V − ∇V · ∇ log =− ∇ log dρt ′ ρt ρ′t Θ Θ      ρ  ρ   ρ   ρ′t t t t ′ − Varρt log − Cov + Covρt log , log log , V − V ρt π π π′ π    ′    ′  ρt ρt − Eρ′t log . + Eρt log ′ π π′   1 c 2 2 By Young’s inequality a · b ≤ 2c ∥a∥ + 2 ∥b∥ , with a = ∇ log ρρt′ and b = ∇V ′ − ∇V for some t c > 0, and integrating with respect to the density ρt , we have that     2 Z Z Z
ρt 1 ρt c 2 ′ ∇V − ∇V · ∇ log dρ ≤ ∇ log dρ + ∇V ′ − ∇V dρt . t t ′ ′ ρ 2c ρ 2 Θ Θ Θ t t H ′ (t) =

16

Choosing c = 12 and using Assumption (A2), we have that Z

∇V ′ − ∇V · ∇ log



Θ

ρt ρ′t





Z dρt ≤

∇ log Θ



Z ∇ log

≤ Θ

ρt ρ′t

 2

ρt ρ′t

 2

dρt +

1 4

Z

∇V ′ − ∇V

2

dρt

Θ

1 dρt + ∆2gradpot . 4

Consequently, we have that   2   Z Z
ρt ρt ′ ∇ log − dρ + ∇V − ∇V · ∇ log dρt t ′ ρ ρ′t Θ Θ t Z   2  Z ρt c 1 2 −1 ∇ log dρ + ∇V ′ − ∇V dρt ≤ t ′ 2c ρ 2 Θ Θ t 1 2 ≤ ∆gradpot . 4 Define Star to be any constant such that log ππ(θ) ′ (θ) ≤ Star for all θ ∈ Θ. Then, using Lemmas 3 and 11,  ′       ′    ρ  ρt 1 (R0′ )2 ρt ρt t + Covρt log , log ≤ Var ≤ exp(−2t). − Varρt log log ρ t π π π′ 4 π′ 16 and

Star R0 exp(−t) and Eρt [s′t ] − Eρ′t [s′t ] ≤ 2R0′ exp(−t). 2 The bound on H(t) follows from integrating both sides of the derived inequality for H ′ (t) and the fact that H(0) = 0 under the common initialization density condition. Under Assumption (A1), Lemma 9 gives Star = 2∆pot , while under Assumption (A1′ ), Lemma 10 gives Star = ∆pot,osc . Applying the two choices of Star above completes the proof. |Covρt (st , g)| ≤

A.2.3

Proof of Theorem 2

Proof. Under the given conditions, Proposition 3 gives that d KL(ρt || ρ′t ) dt   2   Z Z
ρt ρt ′ =− ∇ log dρt + ∇V − ∇V · ∇ log dρt ′ ρt ρ′t Θ Θ     ′    ρ   ρ   ρt ρt t t ′ − Varρt log + Covρt log , log − Cov log , V − V ρ t π π π′ π   ′     ′  ρt ρt − Eρ′t log . + Eρt log ′ π π′   1 ∥b∥2 , with a = ∇ log ρρt′ and b = ∇V ′ − ∇V for some By Young’s inequality a · b ≤ c∥a∥2 + 4c t 0 < c < 1, and integrating with respect to the density ρt , we have that   2   Z Z Z
ρt ρt 1 2 ′ ∇V − ∇V · ∇ log dρ ≤ c ∇ log dρ + ∇V ′ − ∇V dρt . t t ′ ′ ρ ρ 4c Θ Θ Θ t t H ′ (t) =

17

Using Assumption (A2), we have that   2   Z Z Z
ρt 1 ρt ′ ∇ log dρt ≤c dρt + ∇V ′ − ∇V ∇V − ∇V · ∇ log ′ ′ ρ ρ 4c Θ Θ Θ t t   2 Z ρt 1 ∇ log dρt + ∆2gradpot . ≤c ′ ρt 4c Θ   2 R dρt . Then, we have that Define I(t) = Θ ∇ log ρρt′

2

dρt

t



Z −

∇ log Θ

ρt ρ′t

 2

≤ (c − 1)

∇ log Θ

′



∇V − ∇V · ∇ log

dρt + Θ



Z

Z

ρt ρ′t

 2

1 dρt + 4c

Z

∇V ′ − ∇V

2

ρt ρ′t

 dρt

dρt

Θ

1 2 ∆ . 4c gradpot

≤ − (1 − c)I(t) +

Under Assumption (A3) and Lemma 12 and Proposition 4, we have that I(t) ≥ 2 exp(− exp(−t)B)λGibbs H(t) ≥ 2 exp(−B)λGibbs H(t) = 2λ∗SHK H(t) where λ∗SHK = exp(−B)λGibbs and consequently, −(1 − c)I(t) ≤ −2(1 − c) exp(− exp(−t)B)λGibbs H(t) ≤ −2(1 − c)λ∗SHK H(t). Define Star to be any constant such that log ππ(θ) ′ (θ) ≤ Star for all θ ∈ Θ. Then, using Lemmas 3 and 11, we have that     ′    ′    ρ  ρt ρt 1 ρt (R0′ )2 t − Varρt log + Covρt log , log ≤ Var log ≤ exp(−2t). ρ t π π π′ 4 π′ 16 and

Star R0 exp(−t) and Eρt [s′t ] − Eρ′t [s′t ] ≤ 2R0′ exp(−t). 2 1 2 Applying Lemma 13 with c(t) = 2(1 − c) exp(− exp(−t)B)λGibbs and b(t) = bc (t) = 4c ∆gradpot + |Covρt (st , g)| ≤

(R0′ )2 Star R0 exp(−t) + 2R0′ exp(−t), along with the fact that H(0) = 0, we have that 16 exp(−2t) + 2

H(t) = KL(ρt || ρ′t ) ≤

Z t

Z t

 exp −2(1 − c)

0

 exp(− exp(−u)B)λGibbs du bc (s)ds.

s

For the rest of the proof, note that by applying Lemma 13 with constant c(t) ≡ κ and H(0) = 0, we have that Z t
H(t) ≤ e−κ(t−s) A1 + A2 e−s + A3 e−2s ds 0

where A1 :=

∆2gradpot 4c

 ,

A2 := B

 Star +2 , 2

A3 :=

B2 , 16

κ := 2(1 − c) exp(−B)λGibbs .

and then the result follows by evaluating each integral explicitly. Under Assumption (A1), Lemma 9 gives Star = 2∆pot , while under Assumption (A1′ ), Lemma 10 gives Star = ∆pot,osc . Applying the two choices of Star above completes the proof.

18

A.2.4

Application to Differential Privacy results

Proof of Theorem 3 ′

D,D Proof. Let Star be any constant such that

log

πD (θ) D,D′ ≤ Star πD′ (θ)

for all θ ∈ Θ.

Using Equation 7, as derived in the proof of Theorem 1, we have that log

ρt (θ) D,D′ ≤ Star + exp(−t)(RD + RD′ ). ′ ρt (θ)

Using the fact that RD , RD′ ≤ B, we obtain that log

ρD D,D′ D,D′ t (θ) ′) ≤ S ≤ S + exp(−t) (R + R + 2B exp(−t) =: ε(t). D D ′ tar tar ρD t (θ)

Since the inequality holds pointwise, we have for all θ ∈ Θ, ′

D ρD t (θ) ≤ exp(ε(t))ρt (θ) ′

D,D with ε(t) = Star + 2B exp(−t). Then, for all measurable S, we have that Z Z
′ D ′ P (θt ∈ S | D) = ρt (θ)dθ ≤ exp(ε(t)) ρD t (θ)dθ = exp(ε(t))P θt ∈ S | D S

S

Therefore, the mechanism Mt (D) satisfies (ε(t), 0)-DP. Under Assumption (A1), Lemma 9 gives D,D′ D,D′ Star = 2∆pot , while under Assumption (A1′ ), Lemma 10 gives Star = ∆pot,osc . Applying these D,D′ two choices of Star completes the proof. Proof of Theorem 4 ′

D Proof. Let H̄(t) denote any upper bound on H(t) := KL(ρD t || ρt ). Then, using Lemma 17, we have that

P (Mt (D) ∈ S) = P (S) ≤ exp(ε)Q(S) +

H̄(t) H̄(t) = exp(ε)P Mt D′ ∈ S + . ε ε

Therefore, the mechanism Mt (D) satisfies (ε, H̄(t) ε )-DP. Now, we consider the upper bound proved in Theorem 2 as H̄(t). This completes the proof. A.2.5

Auxiliary results

R Lemma 1. If the initial density ρ0 ∈ P(Θ) i.e. Θ dρ0 = 1 and the sequence of densities equation ∂t ρt = ∇ · (∇ρt + ρt ∇V ) − αt ρt , where αt (θ) = {ρt }t≥0 satisfies the transport-reaction R log ρt (θ) − log π(θ) − Θ (log ρt − log π)dρt and π(θ) ∝ exp(−V (θ)) is the Gibbs target determined R R d by the potential V , then dt Θ dρt = 0 and hence Θ dρt = 1 for all t ≥ 0. Proof. Proof follows from Lemma 3.5 of Kondratyev and Vorotnikov (2019). Lemma 2. Let X be any real random variable such that X ∈ [m, M ] almost surely. Then Var(X) ≤

(M − m)2 . 4

19

Proof. The proof is extremely elementary but we still provide it for completeness. Let µ := E[X] ∈ [m, M ]. Note that, since X ∈ [m, M ], we have that 0 ≤ E[(X − m)(M − X)] = (µ − m)(M − µ) − Var(X), and hence Var(X) ≤ (µ − m)(M − µ) ≤

(M − m)2 . 4

Lemma 3. For all t ≥ 0,
1
− Varρ (s) + Covρ s, s′ ≤ Varρ s′ 4 p p Proof. Let a := Varρ (s) ≥ 0, b := Varρ (s′ ) ≥ 0. By Cauchy-Schwarz, q q

Covρ s, s′ ≤ Covρ s, s′ ≤ Varρ (s) Varρ (s′ ) = ab Therefore

− Varρ (s) + Covρ s, s′ ≤ −a2 + ab

Now completing the square, we have that  
b 2 b2 b2 1 −a + ab = − a − + ≤ = Varρ s′ . 2 4 4 4 2

) Lemma 4. For π = exp(−V where Z = Z

R

ρ Θ exp(−V (θ))dθ and u = π , the following identity holds:

∇ρ + ρ∇V = π∇u. Proof. Using ρ = πu, we have that ∇ρ = ∇(πu) = u∇π + π∇u. Also, ρ∇V = (πu)∇V. So ∇ρ + ρ∇V = u∇π + π∇u + πu∇V. Since π = Z −1 exp(−V ) and Z is a constant, ∇π = Z −1 ∇ (exp(−V )) = Z −1 (− exp(−V )∇V ) = −π∇V. Therefore, we have that ∇ρ + ρ∇V = −πu∇V + π∇u + πu∇V = π∇u.

20

Lemma 5. Assume ρt ∈ C 1,2 ([0, T ] × Θ) is a strictly positive solution of the transport-reaction equation (5) i.e. ∂t ρt R= ∇ · (∇ρt + ρt ∇V ) − αt ρt where the (centered) birth-death rate is αt (θ) = log ρt (θ) − log π(θ) − Θ (log ρt − log π)dρt . Then ut = ρπt satisfies the PDE ∂t ut = π −1 ∇ · (π∇ut ) − ut log ut + ut Eρt [log ut ] . Further, assume ut = ρπt > 0 and is smooth. Let st = log ut . Then st satisfies the PDE ∂t st = ∆st + ∥∇st ∥2 + ∇(log π) · ∇st − st + s̄t , where s̄t =

R

Θ st dρt = Eρt [st ] = Eρt [log ut ].

Proof. The transport-reaction equation is given by ∂t ρt = ∇ · (∇ρt + ρt ∇V ) + ρt (log π − log ρt ) − ρt Eρt [log π − log ρt ] . The LHS of the above equation is ∂t ρt = ∂t (πut ) = π∂t ut . Now, we simplify the RHS. Using Lemma 4, we have that ∇ · (∇ρt + ρt ∇V ) = ∇ · (π∇ut ). Further, note that ρt (log π − log ρt ) = (πut ) (log π − (log π + log ut )) = (πut ) (− log ut ) = − πut log ut . and Eρt [log π − log ρt ] = Eρt [− log ut ] = −Eρt [log ut ].Consequently, we have that π∂t ut = ∇ · (π∇ut ) − πut log ut + πut Eρt [log ut ] . and, dividing both sides by π > 0, we have that, ∂t ut = π −1 ∇ · (π∇ut ) − ut log ut + ut Eρt [log ut ] .

(8)

Write ut = exp(st ). Then ∂t ut = ∂t (exp(st )) = exp(st )∂t st Also log ut = st , so u log ut = exp(st )st . Now the weighted diffusion term can be expressed as π −1 ∇ · (π∇ut ) = π −1 ∇ · (π∇ (exp(st ))) . Using ∇ (exp(st )) = exp(st )∇st , we have that π∇ (exp(st )) = π exp(st )∇st . Now taking divergence, we have that ∇ · (π exp(st )∇st ) = (∇ (π exp(st ))) · ∇st + π exp(st )∆st . Note that ∇ (π exp(st )) = exp(st )∇π + π exp(st )∇st . Therefore, we have that (∇ (π exp(st )))·∇st = (exp(st )∇π)·∇st +(π exp(st )∇st )·∇st = exp(st )∇π·∇st +π exp(st )∥∇st ∥2 . 21

So

∇ · (π∇ (exp(st ))) = π exp(st )∆st + π exp(st )∥∇st ∥2 + exp(st )∇π · ∇st .

Dividing by π, we have that π −1 ∇·(π∇ (exp(st ))) = exp(st )∆st +exp(st )∥∇st ∥2 +exp(st )

∇π ·∇st = exp(st ) ∆st + ∥∇st ∥2 + ∇(log π) · ∇st . π

Now plugging everything into the PDE given by Equation (8), we have that
exp(st )∂t st = exp(st ) ∆st + ∥∇st ∥2 + ∇(log π) · ∇st − exp(st )st + exp(st )s¯t Finally, dividing by exp(st ) > 0, we obtain ∂t st = ∆st + ∥∇st ∥2 + ∇(log π) · ∇st − st + s¯t .

Lemma 6. Let s ∈ C 1,2 ([0, T ] × Θ). Define M (t) := max s(t, θ),

m(t) := min s(t, θ).

θ∈Θ

θ∈Θ

Then for each t ∈ [0, T ], the upper Dini derivative satisfies D+ M (t) ≤

max θ∈Argmax s(t,·)

∂t s(t, θ),

and the lower Dini derivative satisfies D− m(t) ≥

min θ∈Argmin s(t,·)

where D+ M (t) = lim sup h↓0

M (t + h) − M (t) , h

∂t s(t, θ),

D− m(t) = lim inf h↓0

m(t + h) − m(t) . h

Proof. Because Θ is compact and s(t, ·) is continuous, maxima and minima are attained for each fixed t. Fix t. For each h > 0, choose θh ∈ Θ such that M (t + h) = s (t + h, θh ) . Then, by definition of M (t) as a maximum at time t, we have that M (t) = max s(t, θ) ≥ s (t, θh ) . θ

Therefore M (t + h) − M (t) = s (t + h, θh ) − M (t) ≤ s (t + h, θh ) − s (t, θh ) . Dividing both sides by h > 0, we have that M (t + h) − M (t) s (t + h, θh ) − s (t, θh ) ≤ . h h

22

Now take lim suph↓0 of both sides, we have that D+ M (t) ≤ lim sup h↓0

s (t + h, θh ) − s (t, θh ) . h

Since Θ is compact, the sequence θh (as h ↓ 0 ) has accumulation points. Take a sequence hn ↓ 0 that realizes the limsup and such that θhn → θ∗ ∈ Θ. By continuity of s, we have s (t, θhn ) → s (t, θ∗ ) . Because s is continuous on the compact set [0, T ] × Θ, it is uniformly continuous. So for every ε > 0, there exists δ > 0 such that
t′ − t < δ ⇒ sup s t′ , θ − s(t, θ) < ε. θ∈Θ

Therefore,

|hn | → 0, θhn → θ∗

=⇒

s (t + hn , θhn ) − s (t, θhn ) → 0.

Let δn := s (t + hn , θhn ) − s (t, θhn ) . Then δn → 0. But by construction s (t + hn , θhn ) = M (t + hn ). Hence s (t, θhn ) = s (t + hn , θhn ) − δn = M (t + hn ) − δn . Since s is uniformly continuous on [0, T ]×Θ and Θ is compact, we have that, for any t, t′ , |M (t) − M (t′ )| ≤ supθ∈Θ |s(t, θ) − s (t′ , θ)|, and the RHS → 0 by uniform continuity. Therefore, the function M (t) = maxθ∈Θ s(t, θ) is continuous in t. Therefore M (t + hn ) → M (t). Combining these results, we have that s (t, θhn ) = M (t + hn ) − δn −→ M (t) − 0 = M (t). Now passing to the limit using continuity of s(t, ·) and θhn → θ∗ , we have that s (t, θ∗ ) = lim s (t, θhn ) = M (t). n→∞

Thus θ∗ attains the maximum of s(t, ·), i.e. θ∗ ∈ Argmax s(t, ·). Now, we proceed to prove that limn→∞ one-variable function of τ ∈ [0, hn ] :

s(t+hn ,θhn )−s(t,θhn ) hn

= ∂t s (t, θ∗ ). Fix n. Consider the

φn (τ ) := s (t + τ, θhn ) Since s ∈ C 1,2 , φn is C 1 in τ and φ′n (τ ) = ∂t s (t + τ, θhn ) By the (one-dimensional) Mean Value Theorem, there exists ξn ∈ (0, hn ) such that φn (hn ) − φn (0) = hn φ′n (ξn ) . 23

Expanding and dividing both sides by hn > 0, we have that s (t + hn , θhn ) − s (t, θhn ) = ∂t s (t + ξn , θhn ) . hn Now take n → ∞. We have ξn ∈ (0, hn ) and hn → 0, hence ξn → 0. Also θhn → θ∗ . Therefore (t + ξn , θhn ) → (t, θ∗ ) Since ∂t s is continuous on [0, T ] × Θ, we conclude ∂t s (t + ξn , θhn ) → ∂t s (t, θ∗ ) Thus

s (t + hn , θhn ) − s (t, θhn ) = ∂t s (t, θ∗ ) n→∞ hn lim

Hence the limsup is bounded by the maximum of ∂t s(t, θ) over maximizers θ ∈ Argmax s(t, ·). That gives the desired inequality. For the lower Dini derivative of the minimum, the argument is analogous: choose yh achieving the minimum at t + h, use m(t) ≤ s (t, yh ), and take lim inf. Lemma 7. Fix t. Assume the domain Θ has no boundary. If θ∗ ∈ Argmax s(t, ·), then ∇s (t, θ∗ ) = 0,

∆s (t, θ∗ ) ≤ 0.

∇s (t, θ∗ ) = 0,

∆s (t, θ∗ ) ≥ 0

If θ∗ ∈ Argmin s(t, ·), then Proof. Let ϕ(θ) := s(t, θ), so ϕ ∈ C 2 (Θ) in the spatial variable (because s ∈ C 1,2 ). Since we assume that Θ is compact and has no boundary, a global maximizer θ∗ (or a global minimizer θ∗ ) is an interior point of Θ. Therefore, standard interior calculus applies i.e. at an interior maximum of a C 2 function, gradient is zero and Hessian is negative semidefinite, implying that ∇s(t, θ∗ ) = 0 and v ⊤ ∇2 s(t, θ∗ )v ≤ 0 for all v ∈ Rd . Consequently, trace of the Hessian i.e. P d ∗ ∗ d 2 Tr(∇2 s(t, θ∗ )) = i=1 e⊤ i ∇ s(t, θ )ei = ∆s(t, θ ) ≤ 0 where ei is the i-th unit vector in R . The case of the Argmin is analogous. Lemma 8. Let s ∈ C 1,2 ([0, T ] × Θ) where Θ is a compact subset of Rd . Define M (t) := max s(t, θ), θ∈Θ

m(t) := min s(t, θ). θ∈Θ

Then for all t ∈ [0, T ], (M (t) − m(t)) ≤ exp(−t) (M (0) − m(0)) . Proof. Let θ∗ ∈ Argmax s(t, ·). We evaluate the PDE at (t, θ∗ ). By Lemma 7, at θ∗ , ∇s (t, θ∗ ) = 0,

∥∇s (t, θ∗ )∥2 = 0,

∆s (t, θ∗ ) ≤ 0.

Also ∇(log π) · ∇st |θ∗ = 0, since ∇st |θ∗ = 0. Thus, from Lemma 5, ∂t s (t, θ∗ ) = ∆s (t, θ∗ ) + 0 + 0 − s (t, θ∗ ) + s̄t ≤ −s (t, θ∗ ) + s̄t . Since s (t, θ∗ ) = M (t), we get

∂t s (t, θ∗ ) ≤ −M (t) + s̄t . 24

Now applying Lemma 6, we have that D+ M (t) ≤ So we have the inequality

max

θ∈Argmax

∂t s(t, θ) ≤ −M (t) + s̄t .

D+ M (t) ≤ −M (t) + s̄t .

Let θ∗ ∈ Argmin s(t, ·). At θ∗ , by Lemma 7, ∥∇s (t, θ∗ )∥2 = 0,

∇s (t, θ∗ ) = 0,

∆s (t, θ∗ ) ≥ 0

Hence from the PDE, ∂t s (t, θ∗ ) = ∆s (t, θ∗ ) + 0 + 0 − s (t, θ∗ ) + s̄t ≥ −s (t, θ∗ ) + s̄t . Since s (t, θ∗ ) = m(t), ∂t s (t, θ∗ ) ≥ −m(t) + s̄t Applying Lemma 6 for the minimum, we have that D− m(t) ≥ Thus

min

θ∈ Argmin

∂t s(t, θ) ≥ −m(t) + s̄t

D− m(t) ≥ −m(t) + s̄t .

Define y(t) := M (t) − m(t). We want an upper bound on the upper Dini derivative D+ y(t). First, note that using lim sup (an − bn ) ≤ lim sup an − lim inf bn , we have that D+ y(t) = D+ (M (t) − m(t)) ≤ D+ M (t) − D− m(t). Therefore, we have that D+ y(t) ≤ (−M (t) + s̄t ) − (−m(t) + s̄t ) = −M (t) + m(t) = −(M (t) − m(t)) = −y(t). So we have the key inequality:

D+ y(t) ≤ −y(t).

Define z(t) := exp(t)y(t). Note that, z(t + h) − z(t) = exp(t + h)y(t + h) − exp(t)y(t) = exp(t) (exp(h)y(t + h) − y(t)) . Divide by h > 0 : z(t + h) − z(t) = exp(t) h



exp(h) − 1 y(t + h) − y(t) y(t + h) + exp(h) h h

 .

Taking lim suph↓0 , using limh→0 (exp(h) − 1) /h = 1, limh→0 exp(h) = 1, and continuity of y (true since s is continuous and max/min on compact sets vary continuously), we have that D+ z(t) = lim sup h↓0

z(t + h) − z(t) = exp(t) y(t) + D+ y(t) . h 25

Using the inequality D+ y(t) ≤ −y(t), D+ z(t) ≤ exp(t)(y(t) − y(t)) = 0. Thus D+ z(t) ≤ 0 for all t. A function with nonpositive upper Dini derivative is nonincreasing, hence z(t) ≤ z(0). That is, exp(t)y(t) ≤ y(0)

y(t) ≤ exp(−t)y(0).

=⇒

This completes the proof. Proposition 2. Let R0 := maxθ∈Θ log

ρ0
π − minθ∈Θ log

 − exp(−t)R0 ≤ log

ρt (θ) π(θ)

ρ0
π . Then for all t ≥ 0 and all θ ∈ Θ,

 ≤ exp(−t)R0 .

Proof. From Lemma 8, max log

ρ 

θ∈Θ

t

π

(θ) − min log

ρ  t

π

θ∈Θ

(θ) ≤ exp(−t)R0 .

We assume that Θ is a compact subset of Rd with no boundary. Now we show log ρπt (θ) ≤

maxθ∈Θ log ρπt (θ) − minθ∈Θ log ρπt (θ) for all θ ∈ Θ. For that, note that, using Lemma 1, we can R show that ut = ρπt satisfies Θ ut π = 1. Since ut > 0, it is impossible that ut > 1 everywhere (else the integral would exceed 1), and impossible that ut < 1 everywhere (else integral would be < 1 ). Therefore ρ  ρ  t t min ut (θ) ≤ 1 ≤ max ut (θ) =⇒ min log ≤ 0 ≤ max log . θ θ θ θ π π
Define st := log ρπt . Then, for all θ ∈ Θ, |st (θ)| ≤ max {max st , − min st } ≤ max st − min st ≤ exp(−t)R0 . This completes the proof. Lemma 9. Define the normalization constants ZD =

′ ′ Θ exp(−VD (θ))dθ and ZD = Θ exp(−VD (θ))dθ exp(−VD′ ) exp(−VD ) and the Gibbs target distributions πD = and πD′ = . Let the potentials V and ZD ZD′ V ′ satisfy Assumption (A1). Then, we have that log ZZD′ ≤ ∆pot . Further, we have that D log ππD′(θ) ≤ 2∆ for any θ ∈ Θ. pot (θ)

R

R

D

Proof. For any θ ∈ Θ, VD (θ) ≤ VD′ (θ) + ∆pot

=⇒

exp(−VD (θ)) ≥ exp(−∆pot ) × exp(−VD′ (θ)).

Integrating over Θ, we have that Z Z ZD = exp(−VD (θ))dθ ≥ exp(−∆pot ) exp(−VD′ (θ))dθ = exp(−∆pot )ZD′ . Θ

Θ

Similarly, from VD (θ) ≥ VD′ (θ) − ∆pot , we get exp(−VD (θ)) ≤ exp(∆pot ) × exp(−VD′ (θ)), hence ZD ≤ exp(∆pot )ZD′ . Taking logs yields

log ZZD′ ≤ ∆pot . D

26

Further, note that, log

ZD ′ πD (θ) . = log exp(−VD (θ))−log ZD −(log exp(−VD′ (θ)) − log ZD′ ) = − (VD (θ) − VD′ (θ))+log πD′ (θ) ZD

Taking absolute values and applying triangle inequality, we have that, for any θ ∈ Θ, log

πD (θ) ZD ′ ≤ |VD (θ) − VD′ (θ)| + log ≤ ∆pot + ∆pot = 2∆pot . πD′ (θ) ZD exp(−VD′ ) and let the ZD ′ log ππD′(θ) (θ) ≤ ∆pot,osc for any

D) Lemma 10. Define the Gibbs target distributions πD = exp(−V and πD′ = ZD

potentials V and V ′ satisfy Assumption (A1′ ). Then, we have that θ ∈ Θ.

D

Proof. Note that, log

ZD ′ πD (θ) = log exp(−VD (θ))−log ZD −(log exp(−VD′ (θ)) − log ZD′ ) = − (VD (θ) − VD′ (θ))+log . πD′ (θ) ZD

Now, let us define a := inf θ∈Θ (VD (θ) − VD′ (θ)) and b := supθ∈Θ (VD (θ) − VD′ (θ)). Clearly, for any θ ∈ θ , a ≤ VD (θ) − VD′ (θ) ≤ b. Now, we have that Z Z exp(−VD′ (θ)) ZD = exp(−VD (θ))dθ =ZD′ exp [− (VD (θ) − VD′ (θ))] × dθ ZD ′ Θ Θ Z =ZD′ exp [− (VD (θ) − VD′ (θ))] dπ ′ (θ). Θ

Consequently, exp(−b) ≤

ZD ZD ′ ≤ b. ≤ exp(−a) ⇐⇒ a ≤ log ′ ZD ZD

Therefore, we have that a − b ≤ log

πD (θ) ≤ b − a. πD′ (θ)

Finally, under Assumption (A1′ ), we have that, for any θ ∈ Θ log

πD (θ) ≤ b − a = sup V (θ) − V ′ (θ) − inf V (θ) − V ′ (θ) ≤ ∆pot,osc . θ∈Θ πD′ (θ) θ∈Θ

Proposition 3. Assume {ρt }t≥0 , {ρ′t }t≥0 ∈ C 1,2 ([0, T ] × Θ) are strictly positive solutions of the transport-reaction equations (5) and (6) on [0, T ]. Then H(t) = KL (ρt ∥ρ′t ) is differentiable and d KL(ρt || ρ′t ) dt   2   Z Z
ρt ρt ′ ∇ log dρt + ∇V − ∇V · ∇ log =− dρt ′ ρt ρ′t Θ Θ     ′    ρ   ρ   ρt ρt t t ′ − Varρt log + Covρt log , log log , V − V − Cov ρ t π π π′ π   ′    ′   ρt ρt + Eρt log − Eρ′t log . π′ π′

H ′ (t) =

27

Proof. Define the log-density ratios wt := log

ρt , ρ′t

st := log

ρt , π

s′t := log

ρ′t , π′

g := log π − log π ′ .

We have the following identity :

wt = log ρt − log ρ′t = (log ρt − log π) − log ρ′t − log π ′ + log π − log π ′ = st − s′t + g. Further, the centered birth-death rates can be expressed as:   αt′ = s′t − Eρ′t s′t .

αt = st − Eρt [st ], Now, we have that

Z

ρt log ′ dρt = H(t) = ρt Θ

Z wt dρt Θ

Differentiating, we have that Z

′

Z

H (t) =

wt (θ) (∂t ρt ( θ))dθ + Θ

(∂t wt ) dρt Θ

Using wt = log ρt − log ρ′t , we have that ∂ t wt = Therefore,

∂t ρt ∂t ρ′t − ′ ρt ρt



d Θ ∂t ρt (θ)dθ = dt

R

Z 

Z (∂t wt ) dρt = Θ

Θ

Using Lemma 1.we have that

R

∂t ρt ∂t ρ′t − ′ . ρt ρt Z ∂t ρt (θ)dθ −

dρt = Θ

θ dρt = 0. Hence, we have that

∂t ρ′t H (t) = wt (θ) (∂t ρt ( θ))dθ + ∂t ρt (θ)dθ − ′ dρt = Θ Θ Θ ρt ′

Z

Z

∂t ρ′t ′ dρt . Θ ρt

Z

Z

∂t ρ′t ′ dρt . Θ ρt

Z

Z wt (θ) (∂t ρt ( θ))dθ − Θ

We can express the Fokker Planck equations in the following form: ∂t ρt = Aρt − αt ρt , ∂t ρ′t = Aρ′t − αt′ ρ′t , Then ′

Aρt := ∇ · (∇ρt + ρt ∇V ),
Aρ′t := ∇ · ∇ρ′t + ρ′t ∇V ′ .

(−αt′ ρ′t ) dρ + (−α ρ )w dθ − ρ dθ t t t t t ′ ρ′t Θ Θ ρt Θ Θ Z Z Z Z Aρ′t Aρt wt dθ − = dρ + − α w dρ + αt′ dρt . t t t t ′ ρ Θ {z } |Θ {z Θ t } | Θ

H (t) =

Z

Z

Aρt wt dθ −

Aρ′t

Z

Z

=:Ibd

=:Idiff

We now analyze Idiff first using integration by parts and simplifying terms. The first term in Idiff is: Z Z ∇ · (∇ρt + ρt ∇V )wt dθ

Aρt wt dθ = Θ

Θ

28

R R Using integration by parts gives Θ (∇ · F )wt dθ = − Θ F · ∇wt dθ with F = ∇ρt + ρt ∇V d. Thus Z Z Aρt wt dθ = − (∇ρt + ρt ∇V ) · ∇wt dθ. Θ

Θ

The second term in Idiff is: Aρ′t

Z −

Z

′ dρt = − Θ ρt

ρt ∇ · ∇ρ′t + ρ′t ∇V ′ dθ. ′ Θ ρt

Again, we integrate by parts with f = ρt /ρ′t and G = ∇ρ′t + ρ′t ∇V ′ : Z Z G · ∇f dθ. f ∇ · Gdθ = − Θ

Θ

So

Z −

ρt

Aρ′t

Θ

Z

dθ = ρ′t

∇ρ′t + ρ′t ∇V ′ · ∇



Θ

ρt ρ′t



ρt ρ′t



dθ

Now, since ρρt′ = exp(wt ), we have that t

 ∇

ρt ρ′t



 = ∇ (exp(wt )) = exp(wt )∇wt =

∇wt .

Therefore ∇ρ′t + ρ′t ∇V ′ ·∇



ρt ρ′t

 =



∇ρ′t + ρ′t ∇V ′ ·

ρt ρ′t



 ∇wt = ρt


∇ρ′t ′ + ∇V ·∇wt = ρt ∇ log ρ′t + ∇V ′ ·∇wt ′ ρt

Also ∇ρt = ρ∇ log ρt , hence (∇ρt + ρt ∇V ) · ∇wt = ρt (∇ log ρt + ∇V ) · ∇wt Combining, we have that Z Z
Idiff = − ρt (∇ log ρt + ∇V ) · ∇wt dθ + ρt ∇ log ρ′t + ∇V ′ · ∇wt dθ Θ Z Θ 
 = ρt ∇ log ρ′t + ∇V ′ − (∇ log ρt + ∇V ) · ∇wt dθ ZΘ 
 = ρt −∇wt + ∇V ′ − ∇V · .∇wt dθ ΘZ Z
=− ∥∇wt ∥2 dρt + ∇V ′ − ∇V · ∇wt dρt . Θ

Θ

Now, we simplify Ibd . Using wt = st − s′t + g, αt = st − Eρt [st ]. and αt′ = s′t − Eρ′t [s′t ]. Let mt := Eρt [st ] and m′t := Eρ′t [s′t ]. Then Z Z
− αt wt dρt = − (st − mt ) st − s′t + g dρt Θ ZΘ Z Z ′ = − (st − mt )st dρt + (st − mt )st dρt − (st − mt )gdρt Θ

Θ = − Varρt (st ) + Covρt (st , s′t ) − Covρt (st , g).

29

Θ

and

Z Θ

αt′ dρt = Eρt [s′t ] − Eρ′t [s′t ].

Combining, we have that,   Ibd = − Varρt (st ) + Covρt (st , s′t ) − Covρt (st , g) + Eρt [s′t ] − Eρ′t [s′t ] . Adding up the expressions for Idiff and Ibd , the proof is complete. Lemma 11. Define Star to be any constant such that log ππ(θ) ′ (θ) ≤ Star for all θ ∈ Θ. Then, for all t ≥ 0, we have that
(R0′ )2 Varρt s′t ≤ exp(−2t) 4 where wt := log

ρt , ρ′t

,

Covρt (st , g) ≤ ∆pot R0 exp(−t)

st := log

ρt , π

s′t := log

and

Eρt [s′t ]−Eρ′t [s′t ] ≤ 2R0′ exp(−t)

g := log π − log π ′

Rt′ := max s′t (θ) − min s′t (θ).

Rt := max st (θ) − min st (θ), θ∈Θ

ρ′t , π′

and

θ∈Θ

θ∈Θ

θ∈Θ

Further, the choices Star = 2∆pot and ∆pot,osc are valid under the assumptions (A1) and (A1′ ), respectively. Proof. Using Lemma 2 and Proposition 2, we have that Varρt (s′t ) ≤ Now, note that by Cauchy-Schwarz, q q |Covρt (st , g)| ≤ Varρt (st ) Varρt (g).

(R0′ )2 4 exp(−2t).

p Varρt (st ) ≤ R0 exp(−t) . Then, we have that 2

Using Lemma 2 and Proposition 2, we have p Varρt (g) ≤ ∥g∥∞ ≤ Star . Thus |Covρt (st , g)| ≤

R0 exp(−t)Star . 2

Finally, note that, For any bounded function h, Eρ [h] − E′ρ [h] ≤ Eρ [h] − E′ρ [h] ≤ |Eρ [h]| + E′ρ [h] ≤ 2∥h∥∞ . Applying this observation with h = s′t and using Proposition 2 to bound∥s′t ∥∞ ≤ Rt exp(−t), the result follows with the choice Star = 2∆pot when Assumption (A1) holds (based on Lemma 9) while the choice Star = ∆pot,osc is valid, based on Lemma 10, when Assumption (A1) holds. Lemma 12. Let σt be the probability measure Rdσt = ρ′t dθ and let σt satisfy log-Sobolev inequality with constant λ(t) > 0 if for all smooth f with f 2 dσt = 1, Z Z
2 2 2 2 Entσt f := f log f dσt ≤ ∥∇f ∥2 dσt λ(t) Then for any probability density ρt , Z ρt I(t) := ∇ log ′ ρt

2

dρt ≥ 2λ(t)KL ρt ∥ρ′t = 2λ(t)H(t) 30

Proof. Let r := ρρt′ . Define f := t

√ r. Then Z

2

Z

2

f = r,

ρt ′ ρ dx = ρ′t t

f dσt =

Z ρt dx = 1

so f is admissible in the LSI. Then the entropy is given by Z Z Z
ρt 2 2 2 ′ Entσt f = f log f dσt = r log rρt dx = ρt log ′ dx = H(t) ρt Now, we have that ∇ log Therefore ρt ∇ log

ρt ρ′t

2

2∇f ρt = ∇ log r = ∇ log f 2 = . ′ ρt f 2

2∇f = f 2 ρ′t · f

Integrating, we have that

Z

= f 2 ρ′t ·

4ρ′t |∇f |2 dx = 4

I(t) =

Z

4∥∇f ∥2 = 4ρ′t ∥∇f ∥2 . f2

|∇f |2 dσt

Now applying LSI, we have that H(t) = Entσt f

2

2 ≤ λ(t)

Z

|∇f |2 dσt =

2 I(t) I(t) · = . λ(t) 4 2λ(t)

Lemma 13 (Gronwall’s inequality). Let H be absolutely continuous and satisfy H ′ (t) ≤ −c(t)H(t) + b(t) for almost every t ∈ [0, T ], where c, b are integrable on [0, T ] and c(t) ≥ 0. Define Z t C(t) := c(u)du 0

Then for all t ∈ [0, T ], H(t) ≤ e−C(t) H(0) +

Z t

e−(C(t)−C(s)) b(s)ds

0

In particular, if H(0) = 0, Z t H(t) ≤

 Z t  exp − c(u)du b(s)ds.

0

s

Lemma 14 (Holley Strook Perturbation principle). (Schlichting, 2019, Theorem A2); (Holley and Stroock, 1986) Let Ω ⊂ Rn and H : Ω → R and ψ : Ω → R be a bounded function. Let µ and µ̃ be the Gibbs measures with potential functions/Hamiltonians H and H + ψ, respectively given by µ ∝ exp(−H)

and

µ̃ ∝ exp(−H − ψ).

Then, R 2 if µ satisfies the Log-Sobolev inequality with LSI constant α i.e. for all smooth f with f dµ = 1, Z Z
2 2 2 2 := Entµ f f log f dµ ≤ ∥∇f ∥2 dµ α 31

then µ̃ satisfies the Log-Sobolev inequality with LSI constant α̃ which satisfies α̃ ≥ exp(− osc(ψ))α where osc(ψ) := supΩ ψ − inf Ω ψ. Proposition 4. Assume π and π ′ satisfy Assumption (A3) with the common LSI constant being λGibbs > 0. Consider the sequence of SHK gradient flow iterates {ρt }t≥0 and {ρ′t }t≥0 corresponding to π and π ′ . Define ρ′ (θ) ρ0 (θ) , s′0 (θ) := log 0′ s0 (θ) := log π(θ) π (θ) and

R0′ := max s′0 (θ) − min s′0 (θ).

R0 := max s0 (θ) − min s0 (θ), θ∈Θ

θ∈Θ

θ∈Θ

θ∈Θ

Further, assume that R0 , R0′ ≤ B for some universal constant B ≥ 0. Then, for every t ≥ 0, the t-th SHK iterate gradient flow iterates ρt and ρ′t also satisfy the Log-Sobolev inequality with a common LSI constant λSHK (t) that satisfies λSHK (t) ≥ exp(− exp(−t)B)λGibbs . Further, uniformly over time t, the sequence of SHK gradient flow iterates {ρt }t≥0 and {ρ′t }t≥0 satisfy the Log-Sobolev inequality with the common LSI constant λSHK that satisfies λSHK ≥ λ∗ := exp(−B)λGibbs . ρ′ (θ)

t (θ) Proof. Define st (θ) := log ρπ(θ) ,

s′t (θ) := log πt′ (θ) . We begin the proof by observing that

   ρt (θ) π(θ) ∝ exp(st (θ)) exp(−V (θ)) = exp (− [V (θ) + (−st (θ))]) ρt (θ) = exp log π(θ) and similarly,

 
ρ′t (θ) ∝ exp − V ′ (θ) + (−s′t (θ))

Note that, using Proposition 2, we have that osc(−st ) := max(−st (θ)) − min(−st (θ)) = − min st (θ) + max st (θ) ≤ exp(−t)R0 ≤ exp(−t)B θ∈Θ

θ∈Θ

θ∈Θ

θ∈Θ

and similarly, we have that osc(−s′t ) := max(−s′t (θ)) − min(−s′t (θ)) = − min s′t (θ) + max s′t (θ) ≤ exp(−t)R0′ ≤ exp(−t)B. θ∈Θ

θ∈Θ

θ∈Θ

θ∈Θ

Hence, using the Holley-Strook perturbation principle (Lemma 14), we have that, for every t ≥ 0, the t-th SHK iterate gradient flow iterates ρt and ρ′t also satisfy the Log-Sobolev inequality with a common LSI constant λSHK (t) that satisfies λSHK (t) ≥ exp(− exp(−t)B)λGibbs . Further, note that λSHK (t) ≥ exp(− exp(−t)B)λGibbs ≥ exp(−B)λGibbs for any t ≥ 0. Therefore, uniformly over time t, the sequence of SHK gradient flow iterates {ρt }t≥0 and {ρ′t }t≥0 satisfy the Log-Sobolev inequality with the common LSI constant λSHK that satisfies λSHK ≥ exp(−B)λGibbs . This completes the proof. Lemma 15. Assume P ≪ Q i.e. P is absolutely continuous with respect to Q, where both P and dP Q are probability measures on Θ. Define the Radon-Nikodym derivative r := dQ . Then for every ε ∈ R, Z Eε (P || Q) =

(r(θ) − exp(ε))+ dQ(θ) Θ

where (x)+ := max{x, 0}. 32

Proof. Fix any measurable S ⊆ Θ. Since P ≪ Q, we can write Z Z Z dP − exp(ε) dQ = (r(θ) − exp(ε))dQ(θ) P (S) − exp(ε)Q(S) = S

S

S

Pointwise, for every θ, it is easy to verify that (r(θ) − exp(ε))1S (θ) ≤ (r(θ) − exp(ε))+ , Integrating both sides w.r.t. Q gives Z P (S) − exp(ε)Q(S) ≤

(r(θ) − exp(ε))+ dQ(θ) Θ

Taking the supremum over S yields Z Eε (P || Q) ≤

(r − exp(ε))+ dQ Θ

To show equality, choose the specific set S ∗ := {θ : r(θ) > exp(ε)} On S ∗ we have (r − exp(ε))+ = r − exp(ε), and on (S ∗ )c we have (r − exp(ε))+ = 0. Therefore Z Z (r − exp(ε))dQ = (r − exp(ε))+ dQ S∗

Θ

But the left-hand side is exactly P (S ∗ ) − exp(ε)Q (S ∗ ). Hence Z ∗ ∗ Eε (P || Q) ≥ P (S ) − exp(ε)Q (S ) = (r − exp(ε))+ dQ Θ

Combined with the earlier inequality, we have that Z Eε (P || Q) = (r − exp(ε))+ dQ. Θ

This completes the proof. Lemma 16. Let ψ(x) := x log x − x + 1,

x ≥ 0,

with the convention 0 log 0 := 0. Then ψ(x) ≥ 0 for all x ≥ 0, and Z KL(P || Q) = ψ(r(θ))dQ(θ) Θ dP where r := dQ is the Radon-Nikodym derivative. Further, consider any a > 1. Then for all x ≥ 0,

(x − a)+ ≤

33

ψ(x) log a

Proof. Note that Z KL(P || Q) =

log Θ

dP dP = dQ

Z

dP dP log dQ = dQ dQ Θ

Z ψ(r(θ))dQ(θ) Θ

R R since rdQ = dP = 1. Now, let us fix a > 1, so log a > 0. Consider ψ(x) = x log x − x + 1. For x > 0, ψ ′ (x) = log x,

ψ ′′ (x) =

1 > 0, x

so ψ is convex on (0, ∞) and continuous on [0, ∞) with ψ(1) = 0 and ψ(x) ≥ 0. Consider the case x ≤ a. Then (x − a)+ = 0, while ψ(x) ≥ 0, hence (x − a)+ = 0 ≤

ψ(x) . log a

Now, consider the case x ≥ a. By convexity, ψ lies above its tangent at a and hence ψ(x) ≥ ψ(a) + ψ ′ (a)(x − a) = ψ(a) + (log a)(x − a). Since ψ(a) ≥ 0, we get ψ(x) ≥ (log a)(x − a). Rearranging gives x−a≤

ψ(x) . log a

But when x ≥ a, (x − a)+ = x − a. So (x − a)+ ≤

ψ(x) . log a

Combining the two cases proves the inequality for all x ≥ 0. Lemma 17. Let P, Q be probability measures on the measurable space (Θ, B) with P ≪ Q. Fix ε > 0. Then, the Hockey-stick divergence and the (exclusive) KL divergence between P and Q satisfies the relation KL(P || Q) Eε (P || Q) ≤ . ε Consequently, for every measurable set S, we have that P (S) ≤ exp(ε)Q(S) +

KL(P || Q) ε

Proof. Let r = dP/dQ. By Lemma 15, Z Eε (P || Q) =

(r − exp(ε))+ dQ

Applying Lemma 16 with a = exp(ε), so log a = ε, and we obtain the pointwise bound (r − exp(ε))+ ≤ 34

ψ(r) . ε

Integrating w.r.t. Q, we have that Z Eε (P || Q) = But

R

ψ(r)dQ = KL(P || Q) because

R

1 (r − exp(ε))+ dQ ≤ ε

Z ψ(r)dQ.

rdQ = 1. Hence

Eε (P || Q) ≤

KL(P || Q) . ε

Finally, since Eε (P || Q) is the supremum of P (S) − exp(ε)Q(S) over S, the bound implies for each measurable S, KL(P || Q) P (S) − exp(ε)Q(S) ≤ , ε i.e. KL(P || Q) . P (S) ≤ exp(ε)Q(S) + ε Lemma 18. Let P, Q be probability measures on the measurable space (Θ, B). Define total variation TV(P || Q) := sup |P (S) − Q(S)|. S∈B

If TV(P || Q) ≤ δ, then for every measurable S, P (S) ≤ Q(S) + δ

and

Q(S) ≤ P (S) + δ.

Equivalently, the (two-sided) (0, δ)-DP inequalities hold for the pair (P, Q). Also, r KL(P || Q) TV(P || Q) ≤ . 2 Finally, let φ : Θ → R be measurable and bounded, ∥φ∥∞ < ∞. Then p |EP [φ] − EQ [φ]| ≤ 2∥φ∥∞ TV(P || Q) ≤ ∥φ∥∞ 2 KL(P || Q). Proof. Fix any S. By definition of TV, P (S) − Q(S) ≤ sup(P (A) − Q(A)) ≤ sup |P (A) − Q(A)| = TV(P, Q) ≤ δ. A

A

Rearrange to get P (S) ≤ Q(S) + δ.qInterchanging the roles of P and Q yields Q(S) ≤ P (S) + δ. Finally, the relation TV(P || Q) ≤ KL(P2 ||Q) is the well-known Pinsker’s inequality. Now, using Pinsker’s inequality, we have that Z |EP [φ] − EQ [φ]| ≤ |φ||d(P − Q)| Z ≤∥φ∥∞ |d(P − Q)| =∥φ∥∞ × 2 TV(P || Q) p ≤∥φ∥∞ 2 KL(P || Q).

35

A.2.6

Proof of Utility analysis

Let us define the volume of a near-optimal sublevel set. For α > 0, define Sα := {x ∈ Θ : f (x) ≤ f∗ + α} ,

mα := Vol (Sα ) ,

m := Vol(Θ).

where all volumes are with respect to the Lebesgue measure. We first characterize how close is the expected value of the objective function f under the exponential mechanism to the true minimum of the function f . Proof of Proposition 1 Proof. Let X ∼ πβ . Define Y := f (X) − f∗ ≥ 0. We first bound the tail probability of Y . Fix α > 0 and r ≥ 0. Then Z 1 exp(−βf (θ))dθ. P(Y ≥ α + r) = πβ ({f ≥ f∗ + α + r}) = Zβ {f ≥f∗ +α+r} On the set {f ≥ f∗ + α + r}, we have exp(−βf (θ)) ≤ exp(−β (f∗ + α + r)). Hence Z exp(−βf (θ))dθ ≤ exp(−β (f∗ + α + r)) Vol(Θ) = exp(−β (f∗ + α + r))m. {f ≥f∗ +α+r}

Also, we can lower bound Zβ using the near-optimal sublevel set Sα as follows: on Sα , f (x) ≤ f∗ + α, so exp(−βf (θ)) ≥ exp(−β (f∗ + α)). Therefore Z Zβ ≥ exp(−βf (θ))dθ ≥ exp(−β (f∗ + α)) Vol (Sα ) = exp(−β (f∗ + α))mα . Sα

Combining, we have that P(Y ≥ α + r) ≤

exp(−β (f∗ + α + r))m m = exp(−βr). exp(−β (f∗ + α))mα mα

Since probabilities are ≤ 1, one can sharpen the above bound to,   m P(Y ≥ α + r) ≤ min 1, exp(−βr) . mα

(9)

R∞ Computing the expectation using the tail bound, we have that E[Y ] = 0 P(Y ≥ t)dt. Splitting the integral at α, Z α Z ∞ Z ∞ E[Y ] = P(Y ≥ t)dt + P(Y ≥ t)dt ≤ α + P(Y ≥ α + r)dr 0

α

0

Using Equation (9) with R := m/mα ≥ 1, we have that Z ∞ E[Y ] ≤ α + min (1, R exp(−βr)) dr. 0

Let r0 := β1 log R. Then for 0 ≤ r ≤ r0 , R exp(−βr) ≥ 1, and for r ≥ r0 , R exp(−βr) ≤ 1. Therefore, Z ∞ Z r0 Z ∞ R min (1, R exp(−βr)) dr = 1dr + R exp(−βr)dr = r0 + exp(−βr0 ). β 0 0 r0 36

But exp(−βr0 ) = exp(− log R) = 1/R, so the second term is 1/β. Thus, Z ∞ 1 1 min (1, R exp(−βr)) dr = log R + β β 0 Hence

1 Eπβ [f ] − f∗ = E[Y ] ≤ α + β

  m log +1 . mα

This completes the proof. Proof of Theorem 5 Proof. Applying Lemma 18 with φ = f and π = πβ : r Eρt [f ] ≤ Eπβ [f ] + Eρt [f ] − Eπβ [f ] ≤ Eπβ [f ] + 2∥f ∥∞

1 KL (ρt ∥πβ ). 2

and then subtracting f∗ from both sides, we obtain r

Eρt [f ] − f∗ ≤ Eπβ [f ] − f∗ + 2∥f ∥∞

1 KL (ρt ∥πβ ). 2

Using Proposition 1, we have that 1 Eπβ [f ] − f∗ ≤ α + β

  m log +1 . mα

Finally, by Lu et al. (2019, Theorem 3.3) applied to π = πβ , for t ≥ t∗ , KL (ρt ∥πβ ) ≤ exp(−(2 − 3δ) (t − t∗ ))KL (ρt0 ∥πβ ) = exp(−(2 − 3δ) (t − t∗ ))H (t0 ) .

A.3

Experiments

In this section, we discus some experiments that we performed to validate our theoretical perturbation bound based results and discuss different aspects of our theoretical results. Setup: The experiments numerically validate the SHK perturbation theory on the one-dimensional torus Θ = [−π, π), a compact boundaryless domain matching the assumptions of the main theorem. All experiments are run on the one-dimensional torus Θ = [−π, π) using a
periodic midpoint grid. For a grid with N cells, the breakpoints are chosen as xi = −π + i + 12 ∆x, ∆x = 2π N . The ′ exp −V ( ) i) Gibbs targets are computed as πi = P exp(−V , πi′ = P exp −Vi ′ ∆x . The SHK PDE solved ( j) j exp(−Vj )∆x j   t (θ) numerically is ∂t ρt = ∇ · (∇ρt + ρt ∇V ) − αt ρt , where αt (θ) = log ρπ(θ) − Eρt log ρπt . The solver uses a periodic finite-volume discretization and RK4 time integration for the SHK transport-reaction PDE. The finite-volume part discretizes the Fokker-Planck transport term, and the reaction term is evaluated pointwise using the centered log-density ratio. The PDEs are not discretized and implemented using discrete particles, but rather they are implemented as direct numerical PDE approximations to the continuum SHK flow so as to keep the correspondence to our continuous-time results as much as possible. 37

Quantities tracked in experiments: Let h(θ) = V (θ) − V ′ (θ). The experiments comb emp (t) = log ρt′ pare the empirical pointwise log-ratio L = maxθ |log ρt (θ) − log ρ′t (θ)| against ρt ∞ the envelopes and bounds presented in our paper. The initialization oscillations are R0 = ρ0
ρ0
′ osc log π , R0 = osc log π′ , where osc(f ) = supθ f (θ) − inf θ f (θ). The (A1) sup-norm sensitivity is ∆pot = ∥V − V ′ ∥∞ = ∥h∥∞ . The (A1′ ) oscillation sensitivity is ∆osc = osc (V − V ′ ) = supθ h(θ) − inf θ h(θ). Our Theorem 1 gives, under Assumption (A1), e−t (R0 + R0′ ). and under Assumption (A1′ ),

log ρρt′ t

∞

log ρρt′

t

∞

≤ 2∆sup +

≤ ∆osc + e−t (R0 + R0′ ). Theorem 1

also implies the Rényi-divergence bound Dα (ρt ∥ρ′t ) ≤ L(t) for every α > 1, where L(t) is the corresponding pointwise log-ratio envelope. For comparison purpose, since we are working in an oracle one-dimensional numerical testbed the exact Gibbs targets are computable, the true target mismatch can be captured by the sharper "exact target-floor" envelope Ltarget (t) = log ππ′ ∞ +e−t (R0 + R0′ ). For privacy experiments, Theorem 3 gives the pure-DP privacy bounds εA1 (t) = 2∆pot + 2Be−t and εA1′ (t) = ∆pot,osc + 2Be−t , where B uniformly bounds the two initialization oscillations RD , RD′ . Experiment 1: For the plot in the left panel of Figure 1, the base potential is taken as V (x) = 1.2(1 − cos(2x)) and the perturbed potential is chosen as V ′ (x) = V (x) + 0.6 sin x + 1. The (A1) bound is safe but very conservative here because the additive constant artificially increases ∥V − V ′ ∥∞ . The (A1′ ) bound is substantially better because oscillation sensitivity ignores additive constants. The exact target-floor bound is closest to the observed behavior.

Figure 1: Experiment 1 For the plot in the right panel of Figure 1, the base potential is V (x) = 4(1 − cos x) and the perturbed potential is V ′ (x) = V (x) − 0.8 cos x. Thus, h(x) = V (x) − V ′ (x) = 0.8 cos x. In this case, 2∥h∥∞ ≈ osc(h), so the (A1) and (A1′ ) floors essentially coincide. This panel shows that the factor of 2 in the Theorem 3 under Assumption (A1) is not merely an artifact of the proof. Under absolute sup-norm control, the stationary target mismatch can get close to 2 ∥V − V ′ ∥∞ . Therefore the correct conclusion is that one cannot remove a factor of 2 in the Assumption (A1) based result in Theorem 1/Theorem 3 i.e. it has a genuine worst-case multiplicative factor of 2, while Assumption (A1′ ) allows an intrinsic sharper formulation when oscillation sensitivity is available.

38

Quantity Empirical SHK log-ratio A1 bound A1′ bound Exact target-floor bound ∥V − V ′ ∥∞ 2∥V − V ′ ∥∞ osc(V − V ′ ) Exact target floor ∥ log(π/π ′ )∥∞

Value 0.644016 3.365895 1.365895 0.809605 1.599920 3.199839 1.199839 0.643549

Table 1: Comparison of empirical and theoretical bounds. Quantity Empirical SHK log-ratio A1 bound A1′ bound Exact target-floor bound ∥V − V ′ ∥∞ 2∥V − V ′ ∥∞ osc(V − V ′ ) Exact target floor

Value 1.505272 1.797173 1.797173 1.698790 0.799893 1.599786 1.599786 1.501403

Table 2: Comparison of empirical and theoretical bounds. Experiment 2: The base potential is V (x) = 1.0(1 − cos(2x)). The perturbation is V ′ (x) = V (x) + 0.45 sin x. The experimental results are reported in Figure 2. In the left panel of Figure 2, the experiment computes Rényi divergences Dα (ρt ||ρt ) for α ∈ {2, 3, 5, 10} and compares it to the bound Ltarget (t). The Rényi bounds are valid but conservative, especially for small α. The conservativeness is expected because Rényi divergence is an integral quantity, while Theorem 1 controls a stronger pointwise likelihood-ratio quantity. The bound is tighter for larger α, since high-order Rényi divergence is more sensitive to pointwise likelihood-ratio peaks. α 2 3 5 10

Empirical Dα 0.055881 0.083185 0.133828 0.228820

Theorem bound Ltarget (t) 0.635315 0.635315 0.635315 0.635315

Table 3: Empirical Rényi divergences and theorem bounds for different values of α. The KL bound given in Theorem 2 uses a Young-inequality parameter c ∈ (0, 1). In the ∆2

LSI-based bound, the main quantities are A1 = gradpot and κ = 2(1 − c)e−B λGibbs and the 4c A1 asymptotic KL plateau behaves like κ . The paper explains that the KL bound is controlled by a balance between forcing from gradient perturbations and LSI contractivity. The constant c trades off these two effects: increasing c decreases A1 , but also decreases κ. In the right panel plot of Figure 2, the solid curve is the asymptotic plateau Aκ1 . This is the limiting KL-bound plateau. The vertical dotted line is c = 12 . The dashed curve evaluates the explicit finite-time KL bound at t = 2. At the grid point closest to c = 1/2, the asymptotic plateau 39

Figure 2: Experiment 2 is essentially minimized, but the finite-time t = 2 value is not minimized. The experiment shows that c = 1/2 is the correct asymptotic balancing choice, but a finite-time certificate may benefit from optimizing c numerically for the runtime of interest. This is a useful practical note for using the KL theorem in certificates. Also, the large value of the KL bound at finite time is due to a conservative placeholder for λGibbs on the torus. Therefore this panel should be presented as an illustration of the c-tradeoff structure, not as a sharp applied KL certificate. Quantity optimized Asymptotic plateau A1 /κ Finite-time bound at t = 2

Minimizing c 0.497588 0.980000

Minimum value 111060.018822 29.683066

Table 4: Optimized values of c for the asymptotic plateau and finite-time bound. Experiment 3: This is the main applied DP experiment. It studies SHK sampling for an exponential-mechanism target in a synthetic torus mean-estimation problem. The paper’s DP application considers dataset-dependent Gibbs targets πD (θ) ∝ exp (−VD (θ)). Theorem 3 turns the pointwise SHK stability bound into pure-DP guarantees, and Theorem 5 separates exponentialmechanism intrinsic utility from finite-time sampling error. The dataset has n = 100 torus-valued observations near 0.25 . A neighboring dataset D′ is created by changing one observation to 1 Pn -2.4. The loss is LD (θ) = n i=1 (1 − cos (θ − yi )). The exponential-mechanism potential is VD (θ) = βLD (θ) for β = 5. The neighboring potential is VD′ (θ) = βLD′ (θ). The experimental results are reported in Figure 3. At t = 7, the computed pure privacy loss is 0.1816 , while the (A1)/(A1′ ) theorem bound is 0.2201 and the exact target-floor envelope is 0.2058 as shown in the top-left panel. The final utility loss is 0.10746 , essentially matching the exact exponential-mechanism utility floor 0.10755 . The computed symmetric hockey-stick divergence at ε = 0.15 is 6.57 × 10−6 , below 1/n2 = 10−4 which shows the attainability of δ values smaller than n12 as enquired by the reviewer. Choosing the utility diagnostic to be U (t) = EρD [LD (θ)] − minθ LD (θ) with the exact exponential-mechanism t utility floor being Uπ = EπD [LD (θ)] − minθ LD (θ)., this experiment also demonstrates that the SHK runtime traces a clear privacy-utility tradeoff-path: early stopping of the SHK dynamics gives smaller privacy loss but worse utility, while longer runtime approaches the exponential-mechanism utility floor and target privacy floor. 40

Figure 3: Experiment 3 Experiment 4: This experiment compares SHK/WFR against the ordinary Langevin/FokkerPlanck flow on a metastable bimodal target. The goal is to show that SHK’s reaction term can give much faster convergence to the target, which improves the utility side of the privacy-utility story. The base potential is V (x) = 2.5(1 − cos(2x)). The perturbation is V ′ (x) = V (x) + 0.35 sin x. The experiment evolves four PDEs: SHK flow under V , SHK flow under V ′ , Langevin/Fokker-Planck flow under V and Langevin/Fokker-Planck flow under V ′ . The experimental results are reported in Figure 4. At t = 6, the SHK pointwise log-ratio is 0.362 , below the SHK theorem envelope 0.414, demonstrating that the SHK theorem bound remains valid and reasonably tight. The stability of SHK and Langevin is similar in this particular perturbation diagnostic, but SHK converges to the target much faster and achieves a much lower value of the KL divergence from the Gibbs target as well, since SHK reaches KL (ρt ∥π) = 2.91 × 10−5 , whereas the Langevin method remains stuck at 0.371. This supports the utility/convergence advantage of the SHK reaction term, even in the context of metastable bimodal distribution landscape.

41

Figure 4: Experiment 4

42