2306/2306.00602.md

Title: Approximate Stein Classes for Truncated Density Estimation

URL Source: https://arxiv.org/html/2306.00602

Markdown Content: Back to arXiv

This is experimental HTML to improve accessibility. We invite you to report rendering errors. Use Alt+Y to toggle on accessible reporting links and Alt+Shift+Y to toggle off. Learn more about this project and help improve conversions.

Why HTML? Report Issue Back to Abstract Download PDF Abstract 1Introduction 2Problem Setup 3Background 4Approximate Stein Classes 5KSD for Truncated Density Estimation 6Experimental Results 7Discussion References License: arXiv.org perpetual non-exclusive license arXiv:2306.00602v2 [stat.ML] null Approximate Stein Classes for Truncated Density Estimation Daniel J. Williams Song Liu Abstract

Estimating truncated density models is difficult, as these models have intractable normalising constants and hard to satisfy boundary conditions. Score matching can be adapted to solve the truncated density estimation problem, but requires a continuous weighting function which takes zero at the boundary and is positive elsewhere. Evaluation of such a weighting function (and its gradient) often requires a closed-form expression of the truncation boundary and finding a solution to a complicated optimisation problem. In this paper, we propose approximate Stein classes, which in turn leads to a relaxed Stein identity for truncated density estimation. We develop a novel discrepancy measure, truncated kernelised Stein discrepancy (TKSD), which does not require fixing a weighting function in advance, and can be evaluated using only samples on the boundary. We estimate a truncated density model by minimising the Lagrangian dual of TKSD. Finally, experiments show the accuracy of our method to be an improvement over previous works even without the explicit functional form of the boundary.

Density Estimation, Truncated Densities, Stein Discrepancies, Score Matching, Parameter Estimation 1Introduction

In truncated density estimation, we are unable to view a full picture of our dataset. We are instead given access to a smaller subsample of data artificially truncated by a boundary. Examples of truncation boundaries include limited number of medical tests resulting in under-reported disease counts, and a country’s borders preventing discoveries of habitat locations. In either case, a complex boundary causes truncation which introduces difficulties in statistical parameter estimation. Regular estimation techniques such as maximum likelihood estimation (MLE) are ill-suited, as we will explain.

When data are truncated, many typical statistical assumptions break down. One fundamental problem with estimation in a truncated space is that the probability density function (PDF), given by

𝑝 𝜽 ⁢ ( 𝒙 )

𝑝 ¯ 𝜽 ⁢ ( 𝒙 ) 𝑍 ⁢ ( 𝜽 ) , 𝑍 ⁢ ( 𝜽 )

∫ 𝑉 𝑝 ¯ 𝜽 ⁢ ( 𝒙 ) ⁢ 𝑑 𝒙 ,

cannot be fully evaluated. In this setup, 𝑉 is the truncated domain which can be highly complex and thus the integration to obtain the normalising constant, 𝑍 ⁢ ( 𝜽 ) , is intractable. This normalising constant could be approximated via numerical integration, such as with Monte Carlo methods (Kalos & Whitlock, 2009), but this comes with a significant computational expense. Recent attention has turned to estimation methods which bypass the calculation of the normalising constant entirely by working with the score function for 𝑝 𝜽 ⁢ ( 𝒙 ) ,

𝝍 𝑝 𝜽

𝝍 𝑝 𝜽 ⁢ ( 𝒙 ) := ∇ 𝒙 log ⁡ 𝑝 𝜽 ⁢ ( 𝒙 )

∇ 𝒙 log ⁡ 𝑝 ¯ 𝜽 ⁢ ( 𝒙 ) .

which uniquely represents a probability distribution. Score-based estimation methods include score matching (Hyvärinen, 2005, 2007), noise-contrastive estimation (Gutmann & Hyvärinen, 2010, 2012) and minimum Stein discrepancies (Stein, 1972; Barp et al., 2019). These methods are computationally fast and accurate, and usually rely on minimising a discrepancy between the score functions for the model density 𝑝 𝜽 ⁢ ( 𝒙 ) and the unknown data density 𝑞 ⁢ ( 𝒙 ) , whose score function is 𝝍 𝑞 := ∇ 𝒙 log ⁡ 𝑞 ⁢ ( 𝒙 ) .

Score-based methods have been applied across many domains, including hypothesis testing (Liu et al., 2016; Chwialkowski et al., 2016; Xu, 2022; Wu et al., 2022), generative modelling (Song & Ermon, 2019; Song et al., 2021; Pang et al., 2020), energy based modelling (Song & Kingma, 2021), and Bayesian posterior estimation (Sharrock et al., 2022). Recently, two lines of work have been proposed for the truncated domain; truncated density estimation via score matching (Yu et al., 2021; Liu et al., 2022; Williams & Liu, 2022), called TruncSM, and truncated goodness-of-fit testing via the kernelised Stein discrepancy (KSD), denoted bounded-domain KSD (bd-KSD) (Xu, 2022).

These two lines of work both use a distance function as a weighting function on the objective. Such a function is chosen in advance such that the boundary conditions required for deriving score matching or KSD hold when the domain is truncated. The computation of this distance function can be challenging when the boundary is complex and high-dimensional, which we will demonstrate later in experiments. Further, these methods rely on knowing a functional form of the boundary, which is not always available.

In this paper, we consider a situation where the functional form of the boundary is not available to us. We can only access the boundary information through a finite set of random samples. As an example, suppose we want to estimate a density model for submissions at an academic conference. We can only observe the accepted papers but not the rejected ones. Furthermore, it is difficult to provide a functional definition of the truncation boundary that distinguishes between the accepted and rejected submissions. However, we can easily identify borderline submissions from the review scores which can be seen as samples of the boundary. In this case, TruncSM and bd-KSD are not applicable due to the lack of a functional definition of the boundary, and classical methods such as MLE are intractable. To our knowledge, there exists no method to estimate a truncated density when there is no functional form of the boundary. To solve this problem, we first define approximate Stein classes and its corresponding Stein discrepancies, which we refer to as truncated kernelised Stein discrepancy (TKSD), which is computationally tractable with only samples from the boundary. By minimising the TKSD, we obtain a truncated density estimator when the boundary’s functional form is unavailable. In experiments, we show that despite the approximate nature of the Stein class, density models can be accurately estimated from truncated observations. We also provide a theoretical justification of the estimator consistency.

Our main contributions are:

•

We introduce approximate Stein classes, which in turn define approximate Stein discrepancies. Unlike earlier approaches, these Stein discrepancies are more relaxed and applicable to a truncated setting.

•

These discrepancies enable density estimation on truncated datasets. This estimator is an extension of earlier Stein discrepancy estimators. We include theoretical and experimental results showing that the TKSD estimator is a consistent and competitive estimator with previous works.

2Problem Setup

The Problem.  We assume the data density, 𝑞 , has support on 𝑉 ⊆ ℝ 𝑑 , whose boundary is denoted as ∂ 𝑉 . We aim to find a model, given by 𝑝 𝜽 , which best estimates 𝑞 . However, there are some significant challenges for the truncated setting: the normalising constant in 𝑝 𝜽 is intractable, and score-based methods rely on a boundary condition which breaks down in this situation. Previous works (Xu, 2022; Liu et al., 2022) do address these issues. However, in this work, we assume we have no functional form of ∂ 𝑉 , and instead, a finite set of samples, { 𝒙 𝑖 ′ } 𝑖

1 𝑚 , which are drawn randomly from the boundary. To our best knowledge, no existing density estimation methods can be applied directly.

The Aims.  We aim to use unnormalised models to estimate a truncated density, bypassing the evaluation of the normalising constant. We also aim to construct an estimator that does not require a functional form of the boundary, but can still adjust to the boundary and the dataset adaptively. This will lead to an estimator which is data-driven and flexible, not relying on a pre-defined weighting function, unlike previous works by Xu (2022) and Liu et al. (2022).

Before explaining our proposed solution, we introduce prior methods for measuring discrepancies for unnormalised densities.

3Background

Statistical density estimation is often performed by minimising a divergence between the data density, 𝑞 ⁢ ( 𝒙 ) , and the model density, 𝑝 𝜽 ⁢ ( 𝒙 ) . Since truncated densities have intractable normalising constants, we introduce divergence measures suited for unnormalised densities and discuss their generalizations to truncated supports. These methods rely on Stein’s identity, which we will introduce foremost.

3.1Stein’s Identity

Originating from Stein’s method (Stein, 1972; Chen et al., 2011), a Stein class of functions enables the construction of a family of discrepancy measures (Barp et al., 2019).

Definition 3.1.

Let 𝑞

𝑞 ⁢ ( 𝒙 ) be any smooth probability density supported on ℝ 𝑑 and let 𝒮 𝑞 : ℱ 𝑑 → ℝ be a map. ℱ 𝑑 is a Stein class of functions, if for any 𝒇 ∈ ℱ 𝑑 ,

𝔼 𝑞 ⁢ [ 𝒮 𝑞 ⁢ 𝒇 ⁢ ( 𝒙 ) ]

0 ,

(1)

where 𝒮 𝑞 is called a Stein operator (Gorham & Mackey, 2015).

We refer to Equation 1 as the Stein identity, which underpins a lot of existing work in unnormalised modelling. The Langevin Stein operator (Gorham & Mackey, 2015) on 𝑝 𝜽 ⁢ ( 𝒙 ) ,

𝒮 𝑝 𝜽 ⁢ 𝒇 ⁢ ( 𝒙 )

𝒯 𝑝 𝜽 ⁢ 𝒇 ⁢ ( 𝒙 ) := ∑ 𝑙

1 𝑑 𝜓 𝑝 𝜽 , 𝑙 ⁢ ( 𝒙 ) ⁢ 𝑓 𝑙 ⁢ ( 𝒙 ) + ∂ 𝑥 𝑙 𝑓 𝑙 ⁢ ( 𝒙 ) ,

where 𝜓 𝑝 𝜽 , 𝑙 ⁢ ( 𝒛 ) := ∂ 𝑧 𝑙 log ⁡ 𝑝 𝜽 ⁢ ( 𝒛 ) , is independent of the normalising constant, 𝑍 ⁢ ( 𝜽 ) . 𝑝 𝜽 is involved in the Stein operator only via its ‘proxy’, the score function, 𝝍 𝑝 𝜽 . When this Langevin Stein operator is used, it is straightforward to see that Equation 1 holds:

𝔼 𝑞 ⁢ [ 𝒯 𝑞 ⁢ 𝒇 ⁢ ( 𝒙 ) ]

∫ ℝ 𝑑 𝑞 ⁢ ( 𝒙 ) ⁢ ( ∑ 𝑙

1 𝑑 𝜓 𝑞 , 𝑙 ⁢ 𝑓 𝑙 ⁢ ( 𝒙 ) + ∂ 𝑥 𝑙 𝑓 𝑙 ⁢ ( 𝒙 ) ) ⁢ 𝑑 𝒙

∑ 𝑙

1 𝑑 ∫ ℝ 𝑑 ∂ 𝑥 𝑙 𝑞 ⁢ ( 𝒙 ) ⁢ 𝑓 𝑙 ⁢ ( 𝒙 ) + 𝑞 ⁢ ( 𝒙 ) ⁢ ∂ 𝑥 𝑙 𝑓 𝑙 ⁢ ( 𝒙 ) ⁢ 𝑑 ⁢ 𝒙

0 ,

where the last equality holds due to integration by parts and the fact that 𝑞 ⁢ ( 𝒙 ) vanishes at infinity:

lim ‖ 𝒙 ‖ → ∞ 𝑞 ⁢ ( 𝒙 )

0 .

(2)

This assumption is critical, and is a key focus of research for this paper. It holds for many densities supported on ℝ 𝑑 , such as the Gaussian distribution or the Gaussian mixture distribution. In the rest of this paper, we refer to this condition as the boundary condition, as it describes the behaviour of 𝑞 ⁢ ( 𝒙 ) at the boundary of its domain.

3.2Divergence for Unnormalised Densities

When 𝒙 ∈ ℝ 𝑑 , and the boundary condition Equation 2 holds, we describe two computationally tractable discrepancy measures for unnormalised density models 𝑝 𝜃 ⁢ ( 𝒙 ) : the Stein discrepancy and the score matching divergence. Both divergences rely on Stein’s identity to derive a tractable form.

3.2.1Classical Stein Discrepancy

Gorham & Mackey (2015) use Stein’s identity to define a Stein discrepancy: the supremum of the differences between expected Stein operators for two densities 𝑞 ⁢ ( 𝒙 ) and 𝑝 𝜽 ⁢ ( 𝒙 ) ,

𝒟 𝑆 ⁢ 𝐷 ⁢ ( 𝑝 𝜽 | 𝑞 ) :

sup 𝒇 ∈ ℱ 𝑑 ( 𝔼 𝑞 ⁢ [ 𝒯 𝑝 𝜽 ⁢ 𝒇 ⁢ ( 𝒙 ) ] − 𝔼 𝑝 𝜽 ⁢ [ 𝒯 𝑝 𝜽 ⁢ 𝒇 ⁢ ( 𝒙 ) ] )

sup 𝒇 ∈ ℱ 𝑑 𝔼 𝑞 ⁢ [ 𝒯 𝑝 𝜽 ⁢ 𝒇 ⁢ ( 𝒙 ) ] ,

(3)

where the second line holds as ℱ 𝑑 is a Stein class. The Stein discrepancy can be interpreted as the maximum violation of Stein’s identity. 𝒇 is referred to as the discriminatory function, as it discriminates between 𝑞 ⁢ ( 𝒙 ) and 𝑝 𝜽 ⁢ ( 𝒙 ) . However, the supremum in Equation 3 across ℱ 𝑑 is a challenging problem for optimisation (Gorham & Mackey, 2015).

Stein discrepancies have seen a lot of recent development, including extensions to non-Euclidean domains (Shi et al., 2021; Xu & Matsuda, 2021), discrete operators (Yang et al., 2018), stochastic operators (Gorham et al., 2020) and diffusion-based operators (Gorham & Mackey, 2015; Gorham et al., 2020).

3.2.2Kernelised Stein Discrepancy (KSD)

When we restrict the function class over which the supremum is taken to a Reproducing Kernel Hilbert Space (RKHS), we can derive the Kernelised Stein discrepancy (KSD), for which we follow a similar definition to Chwialkowski et al. (2016) and Liu et al. (2016).

First, let 𝒢 be an RKHS equipped with positive definite kernel 𝑘 , and let 𝒢 𝑑 denote the product RKHS with 𝑑 elements, where 𝒈

( 𝑔 1 , … , 𝑔 𝑑 ) ∈ 𝒢 𝑑 , and is defined with inner product ⟨ 𝒈 , 𝒈 ′ ⟩ 𝒢 𝑑

∑ 𝑖

1 𝑑 ⟨ 𝑔 𝑖 , 𝑔 𝑖 ′ ⟩ 𝒢 and norm ‖ 𝒈 ‖ 𝒢 𝑑

∑ 𝑖

1 𝑑 ⟨ 𝑔 𝑖 , 𝑔 𝑖 ⟩ 𝒢 . By the reproducing property, any evaluation of 𝒈 ∈ 𝒢 𝑑 can be written as

𝒈 ⁢ ( 𝒙 )

⟨ 𝒈 , 𝑘 ⁢ ( 𝒙 , ⋅ ) ⟩ 𝒢 𝑑

∑ 𝑖

1 𝑑 ⟨ 𝑔 𝑖 , 𝑘 ⁢ ( 𝒙 , ⋅ ) ⟩ 𝒢 .

(4)

Taking the supremum over 𝒢 𝑑 , and including the restriction of 𝒈 to the RKHS unit ball, i.e. ‖ 𝒈 ‖ 𝒢 𝑑 ≤ 1 , gives rise to the KSD

𝒟 KSD ⁢ ( 𝑝 𝜽 | 𝑞 )
:= sup 𝒈 ∈ 𝒢 𝑑 , ‖ 𝒈 ‖ 𝒢 𝑑 ≤ 1 𝔼 𝑞 ⁢ [ 𝒯 𝑝 𝜽 ⁢ 𝒈 ⁢ ( 𝒙 ) ]

‖ 𝔼 𝑞 ⁢ [ 𝒯 𝑝 𝜽 ⁢ 𝑘 ⁢ ( 𝒙 , ⋅ ) ] ‖ 𝒢 𝑑 .

(5)

The KSD has a closed-form expression as indicated by Equation 5. Moreover, the squared KSD can be expanded to a double expectation

𝒟 KSD ⁢ ( 𝑝 𝜽 | 𝑞 ) 2

‖ 𝔼 𝑞 ⁢ [ 𝒯 𝑝 𝜽 ⁢ 𝑘 ⁢ ( 𝒙 , ⋅ ) ] ‖ 𝒢 𝑑 2

𝔼 𝒙 ∼ 𝑞 ⁢ 𝔼 𝒚 ∼ 𝑞 ⁢ [ ∑ 𝑙

1 𝑑 𝑢 𝑙 ⁢ ( 𝒙 , 𝒚 ) ]

(6)

where

𝑢 𝑙 ⁢ ( 𝒙 , 𝒚 )

𝜓 𝑝 , 𝑙 ⁢ ( 𝒙 ) ⁢ 𝜓 𝑝 , 𝑙 ⁢ ( 𝒚 ) ⁢ 𝑘 ⁢ ( 𝒙 , 𝒚 ) + 𝜓 𝑝 , 𝑙 ⁢ ( 𝒙 ) ⁢ ∂ 𝑦 𝑙 𝑘 ⁢ ( 𝒙 , 𝒚 )

• 𝜓 𝑝 , 𝑙 ⁢ ( 𝒚 ) ⁢ ∂ 𝑥 𝑙 𝑘 ⁢ ( 𝒙 , 𝒚 )
• ∂ 𝑥 𝑙 ∂ 𝑦 𝑙 𝑘 ⁢ ( 𝒙 , 𝒚 ) .

(7)

This divergence can be fully evaluated using samples from 𝑞 ⁢ ( 𝒙 ) to approximate the expectation in Equation 6. Further, Chwialkowski et al. (2016) showed that 𝒟 KSD ⁢ ( 𝑝 𝜽 | 𝑞 )

0 if and only if 𝑝 𝜽

𝑞 , making 𝒟 KSD ⁢ ( 𝑝 𝜽 | 𝑞 ) a good discrepancy measure between distributions.

3.2.3Score Matching

The score matching (or the Fisher-Hyvärinen) divergence, initially developed by Hyvärinen (2005), is the expected squared difference between the score functions for the two densities 𝑝 𝜽 ⁢ ( 𝒙 ) and 𝑞 ⁢ ( 𝒙 ) :

𝒟 𝑆 ⁢ 𝑀 ⁢ ( 𝑝 𝜽 | 𝑞 )

𝔼 𝑞 ⁢ [ ‖ 𝒉 ⁢ ( 𝒙 ) 1 / 2 ⊙ ( 𝝍 𝑞 − 𝝍 𝑝 ) ‖ 2 ] ,

(8)

where ⊙ denotes element-wise multiplication. The inclusion of the weighting function 𝒉 ⁢ ( 𝒙 ) yields the generalised score matching divergence (Lin et al., 2016; Yu et al., 2016, 2019), and 𝒉 ⁢ ( 𝒙 )

𝟏 yields the classic score matching divergence.

It can be seen that 𝒟 𝑆 ⁢ 𝑀 ⁢ ( 𝑝 𝜽 | 𝑞 ) is simply the squared difference between two Langevin Stein operators 𝒯 𝑝 𝜽 ⁢ ℎ 𝑙 ⁢ ( 𝒙 ) and 𝒯 𝑞 ⁢ ℎ 𝑙 ⁢ ( 𝒙 ) . Using Equation 1, 𝒟 𝑆 ⁢ 𝑀 ⁢ ( 𝑝 𝜽 | 𝑞 ) can be rewritten as

𝔼 𝑞 ⁢ [ ∑ 𝑙

1 𝑑 ℎ 𝑙 ⁢ ( 𝒙 ) ⁢ ( 𝜓 𝑝 , 𝑙 2 + 2 ⁢ ∂ 𝑥 𝑙 𝜓 𝑝 , 𝑙 ) + ∂ 𝑥 𝑙 ℎ 𝑙 ⁢ ( 𝒙 ) ⁢ 𝜓 𝑝 , 𝑙 ] + 𝐶 𝑞 ,

where 𝐶 𝑞

𝔼 𝑞 ⁢ [ 𝝍 𝑞 ⊤ ⁢ 𝝍 𝑞 ] can be considered a constant which can be safely ignored when minimising with respect to 𝜽 .

3.3Divergence for Densities with a Truncated Support

Let 𝑉 ⊂ ℝ 𝑑 be a domain whose boundary is denoted by ∂ 𝑉 . The boundary condition of the density 𝑞 ⁢ ( 𝒙 ) given in Equation 2 needs to hold on the boundary ∂ 𝑉 , i.e., the truncated density 𝑞 ⁢ ( 𝒙 ′ )

0 , ∀ 𝒙 ′ ∈ ∂ 𝑉 . However, this is, in general, not true for truncated densities. For example, a 1D truncated unit Gaussian distribution within the interval [ − 1 , 1 ] has non-zero density at the boundary of the support at exactly 𝑥

− 1 and 𝑥

1 . When the boundary condition breaks down, the function families presented for classical SD, KSD and score matching are no longer Stein classes, and these divergences are no longer computationally tractable.

We outline two recent methods for circumventing this issue by modifying the KSD and the score matching divergence.

3.3.1Bounded-Domain KSD (bd-KSD)

Motivated by performing goodness-of-fit testing on truncated domains, Xu (2022) propose a modified Stein operator, given by

𝒯 𝑝 , ℎ ⁢ 𝒈 ⁢ ( 𝒙 )

∑ 𝑙

1 𝑑 𝜓 𝑝 , 𝑙 ⁢ 𝑔 𝑙 ⁢ ( 𝒙 ) ⁢ ℎ ⁢ ( 𝒙 ) + ∂ 𝑥 𝑙 ( 𝑔 𝑙 ⁢ ( 𝒙 ) ⁢ ℎ ⁢ ( 𝒙 ) )

(9)

for 𝒈 ∈ 𝒢 𝑑 , where ℎ ⁢ ( 𝒙 ) is a weighting function for which ℎ ⁢ ( 𝒙 ′ )

0 ⁢ ∀ 𝒙 ′ ∈ ∂ 𝑉 . This modified Stein operator relies on the boundary conditions on ℎ instead of 𝑞 . This condition can be satisfied by choosing ℎ carefully.

Using the Stein operator in Equation 3 and taking the supremum over 𝒈 ∈ 𝒢 𝑑 gives an alternative definition to KSD for bounded domains, called bounded-domain kernelised Stein discrepancy (bd-KSD):

𝒟 bd-KSD ⁢ ( 𝑝 𝜽 | 𝑞 ) 2

‖ 𝔼 𝑞 ⁢ [ 𝒯 𝑝 𝜽 , ℎ ⁢ 𝑘 ⁢ ( 𝒙 , ⋅ ) ] ‖ 𝒢 𝑑 2 .

The form of ℎ is not explicitly defined, but the authors recommend a distance function. For example, if 𝑉 is the unit ball, ℎ ⁢ ( 𝒙 )

1 − ‖ 𝒙 ‖ 𝑏 for a chosen power 𝑏 .

3.3.2Truncated Score Matching (TruncSM)

When the support of 𝑞 is the non-negative orthant, ℝ + 𝑑 , Hyvärinen (2007) and Yu et al. (2019) impose restrictions on the weighting function 𝒉 in the score matching divergence, given in Equation 8, such that 𝒉 ⁢ ( 𝒙 ) → 0 as ‖ 𝒙 ‖ → 0 , for example 𝒉 ⁢ ( 𝒙 )

𝒙 . Yu et al. (2021) and Liu et al. (2022) generalised this constraint on 𝒉 to any bounded domain 𝑉 , imposing the restrictions ℎ 𝑙 ⁢ ( 𝒙 ) > 0 ⁢ ∀ 𝑙 and 𝒉 ⁢ ( 𝒙 ′ )

𝟎 for all 𝒙 ′ ∈ ∂ 𝑉 .

Liu et al. (2022) showed that maximising a Stein discrepancy with respect to 𝒉 gives a solution 𝒉 0

( ℎ 0 , … , ℎ 0 ) , where

ℎ 0

min 𝒙 ′ ∈ ∂ 𝑉 ⁡ dist ⁢ ( 𝒙 , 𝒙 ′ ) ,

(10)

the smallest distance between 𝒙 and the boundary ∂ 𝑉 . Liu et al. (2022) proposed the use of several distance functions such as the ℓ 1 and ℓ 2 distance. The generalised score matching divergence with ℎ 0 is referred to as TruncSM.

4Approximate Stein Classes

So far, previous works have assumed a functional form of the truncation boundary, so that ℎ can be precisely designed and Stein’s identity holds exactly. In our setting, the functional form of the truncation boundary is unavailable, making the design of a Stein class infeasible; we cannot design a class of functions with appropriate boundary conditions that satisfy Stein’s identity exactly. However, the truncation boundary is known to us approximately as a set of boundary points, and so we can design a set of functions such that Stein’s identity holds ‘approximately’, as we will show below.

Let us first define an approximate Stein class and an approximate Stein identity.

Definition 4.1.

Let 𝑞

𝑞 ⁢ ( 𝒙 ) be a smooth probability density function on 𝑉 ⊆ ℝ 𝑑 . ℱ ~ 𝑚 𝑑 is an approximate Stein class of 𝑞 , if for all 𝒇 ~ ∈ ℱ ~ 𝑚 𝑑 ,

𝔼 𝑞 ⁢ [ 𝒮 𝑞 , 𝑚 ⁢ 𝒇 ~ ⁢ ( 𝒙 ) ]

𝑂 𝑃 ⁢ ( 𝜀 𝑚 ) ,

(11)

where 𝜀 𝑚 is a monotonically decreasing function of 𝑚 , and 𝒮 𝑞 , 𝑚 is a Stein operator that depends on 𝑚 in some way. 𝑂 𝑃 ⁢ ( 𝜀 𝑚 ) denotes a sequence indexed by 𝑚 which is bounded in probability by 𝜀 𝑚 .

We denote Equation 11 as the approximate Stein identity, and the approximate Stein class ℱ ~ 𝑚 𝑑 can be written more simply as

ℱ ~ 𝑚 𝑑

{ 𝒇 ~ : 𝑉 → ℝ | 𝔼 𝑞 ⁢ [ 𝒮 𝑞 , 𝑚 ⁢ 𝒇 ~ ⁢ ( 𝒙 ) ]

𝑂 𝑃 ⁢ ( 𝜀 𝑚 ) } .

(12)

The classical Stein class of functions given by Equation 1 requires Stein’s identity to hold, whereas this approximate Stein class Equation 12 defines a set of functions for which 𝔼 𝑞 ⁢ [ 𝒮 𝑞 , 𝑚 ⁢ 𝒇 ~ ⁢ ( 𝒙 ) ] is bounded by a decreasing sequence. Similarly to the classical Stein discrepancy, we propose the use of the Langenvin Stein operator, i.e. 𝒮 𝑞 , 𝑚

𝒯 𝑞 , 𝑚 . We aim to show this is a flexible class which can be used across various applications, of which we provide two examples below.

Example: Latent Variable Models.

Kanagawa et al. (2019) presented a variation of KSD for testing the goodness-of-fit of models with unobserved latent variables 𝒛 , where the density of 𝒙 is given by 𝑞 ⁢ ( 𝒙 )

∫ ℝ 𝑑 𝑞 ⁢ ( 𝒙 | 𝒛 ) ⁢ 𝑞 ⁢ ( 𝒛 ) ⁢ 𝑑 𝒛 , and thus the score function can be written as

𝝍 𝑞 ⁢ ( 𝒙 )

∇ 𝒙 𝑞 ⁢ ( 𝒙 ) 𝑞 ⁢ ( 𝒙 )

∫ ℝ 𝑑 ∇ 𝒙 𝑞 ⁢ ( 𝒙 | 𝒛 ) 𝑞 ⁢ ( 𝒙 | 𝒛 ) ⋅ 𝑞 ⁢ ( 𝒙 | 𝒛 ) ⁢ 𝑞 ⁢ ( 𝒛 ) 𝑞 ⁢ ( 𝒙 ) ⁢ 𝑑 𝒛

𝔼 𝑞 ⁢ ( 𝒛 | 𝒙 ) ⁢ [ 𝝍 𝑞 ⁢ ( 𝒙 | 𝒛 ) ] .

(13)

We show that this existing modification of KSD gives rise to an Approximate Stein Class. To evaluate the expectation over 𝑞 ⁢ ( 𝒛 | 𝒙 ) , Kanagawa et al. (2019) recommend approximating the expectation with a Monte Carlo estimate

𝔼 𝑞 ⁢ ( 𝒛 | 𝒙 ) ⁢ [ 𝝍 𝑞 ⁢ ( 𝒙 | 𝒛 ) ]

1 𝑚 ⁢ ∑ 𝑖

1 𝑚 𝝍 𝑞 ⁢ ( 𝒙 | 𝒛 𝑖 ) + 𝑂 𝑃 ⁢ ( 𝜀 𝑚 ) ,

(14)

where we assume we have access to 𝑚 unbiased samples { 𝒛 𝑖 } 𝑖

1 𝑚 ∼ 𝑞 ⁢ ( 𝒛 | 𝒙 ) , and 𝑂 𝑃 ⁢ ( 𝜀 𝑚 ) is the Monte Carlo approximation error. This approximation leads to

𝔼 𝑞 ⁢ [ 𝒯 𝑞 ⁢ 𝒈 ⁢ ( 𝒙 ) ]

𝑂 𝑃 ⁢ ( 𝜀 𝑚 ) ≠ 0

and therefore this variation of KSD uses an Approximate Stein Class. See Section A.1 for more details.

5KSD for Truncated Density Estimation

Let 𝑞 ⁢ ( 𝒙 ) be a smooth probability density function with truncated support 𝑉 ⊂ ℝ 𝑑 with boundary ∂ 𝑉 . When 𝑞 ⁢ ( 𝒙 ) has a truncated support, 𝒢 𝑑 is not a Stein class. To show this, let 𝒈 ∈ 𝒢 𝑑 , then Stein’s identity can be written as

𝔼 𝒯 𝑞 ⁢ 𝒈 ⁢ ( 𝒙 )

∫ 𝑉 𝑞 ⁢ ( 𝒙 ) ⁢ ( ∑ 𝑙

1 𝑑 𝜓 𝑝 𝜽 , 𝑙 ⁢ ( 𝒙 ) ⁢ 𝑔 𝑙 ⁢ ( 𝒙 ) + ∂ 𝑥 𝑙 𝑔 𝑙 ⁢ ( 𝒙 ) ) ⁢ 𝑑 𝒙

∑ 𝑙

1 𝑑 ∫ 𝑉 ∂ 𝑥 𝑙 𝑞 ⁢ ( 𝒙 ) ⁢ 𝑔 𝑙 ⁢ ( 𝒙 ) + 𝑞 ⁢ ( 𝒙 ) ⁢ ∂ 𝑥 𝑙 𝑔 𝑙 ⁢ ( 𝒙 ) ⁢ 𝑑 ⁢ 𝒙

∮ ∂ 𝑉 𝑞 ⁢ ( 𝒙 ) ⁢ ∑ 𝑙

1 𝑑 𝑔 𝑙 ⁢ ( 𝒙 ) ⁢ u ^ 𝑙 ⁢ ( 𝒙 ) ⁢ 𝑑 ⁢ 𝑠 ,

(15)

where ∮ ∂ 𝑉 is the surface integral over the boundary ∂ 𝑉 , u ^ 1 ⁢ ( 𝒙 ) , … , u ^ 𝑑 ⁢ ( 𝒙 ) are the unit outward normal vectors on ∂ 𝑉 and 𝑑 ⁢ 𝑠 is the surface element on ∂ 𝑉 .

To satisfy the Stein identity, Equation 15 must equal zero. In the untruncated setting, Equation 15 is zero due to the boundary condition on 𝑞 ⁢ ( 𝒙 ) , but in the truncated setting the density is significantly nonzero on the boundary at ∂ 𝑉 . Prior methods such as Xu (2022) choose a pre-defined weighting function for which Equation 15 is exactly zero at the boundary. We instead aim to show that Equation 15 is 𝑂 𝑃 ⁢ ( 𝜀 𝑚 ) under an approximate Stein class, detailed in the remainder of this section.

5.1Approximate Stein Class for Truncated Densities

Let us first consider a setting where the boundary ∂ 𝑉 is known analytically. Define a modified product RKHS as

𝒢 0 𝑑

{ 𝒈 ∈ 𝒢 𝑑 | 𝒈 ⁢ ( 𝒙 ′ )

𝟎 ⁢ ∀ 𝒙 ′ ∈ ∂ 𝑉 , ‖ 𝒈 ‖ 𝒢 𝑑 2 ≤ 1 } .

(16) Lemma 5.1.

Let 𝑞 be a smooth density supported on 𝑉 . For any 𝐠 ∈ 𝒢 0 𝑑 , then

𝔼 𝑞 ⁢ [ 𝒯 𝑞 ⁢ 𝒈 ⁢ ( 𝒙 ) ]

0 .

(17)

Similar to the classic Stein’s identity, the proof follows from applying a simple integration by parts, see Section A.2. Lemma 5.1 shows that 𝒢 0 𝑑 is a proper Stein class of 𝑞 . 𝒢 0 𝑑 defines a large class of functions, for which the proposed operator by Xu (2022) given in Equation 9 is one such example of a function from this family.

Let us now consider the setting where ∂ 𝑉 is not known exactly. The information about the boundary is provided by ∂ 𝑉 ~

{ 𝒙 𝑖 ′ ′ } 𝑖 ′

1 𝑚 , a finite set of points randomly sampled from ∂ 𝑉 . Define

𝒢 0 , 𝑚 𝑑

{ 𝒈 ∈ 𝒢 𝑑 | 𝒈 ⁢ ( 𝒙 ′ )

𝟎 ⁢ ∀ 𝒙 ′ ∈ ∂ 𝑉 ~ , ‖ 𝒈 ‖ 𝒢 𝑑 2 ≤ 1 } ,

(18)

which can be considered as an approximate version of 𝒢 0 𝑑 using the finite set ∂ 𝑉 ~ . The benefit of using 𝒢 0 , 𝑚 𝑑 over 𝒢 0 𝑑 is that this class can be constructed using only ‘partial’ boundary information, i.e., ∂ 𝑉 ~ , without knowing the explicit expression of ∂ 𝑉 .

First, we show specific properties of the relationship between ∂ 𝑉 ~ and ∂ 𝑉 .

Lemma 5.2.

Let 𝐠 ∈ 𝒢 0 𝑑 and 𝐠 ~ ∈ 𝒢 0 , 𝑚 𝑑 . Assume that ∂ 𝑉 ~ is 𝜀 𝑚 -dense in ∂ 𝑉 with some probability. Further assume that 𝑔 𝑙 and 𝑔 ~ 𝑙 are 𝐶 -Lipschitz continuous for all 𝑙

1 , … , 𝑑 . Then

| 𝑔 𝑙 ⁢ ( 𝒙 ′ ) − 𝑔 ~ 𝑙 ⁢ ( 𝒙 ′ ) |

𝑂 𝑃 ⁢ ( 𝜀 𝑚 )

for any 𝐱 ′ ∈ ∂ 𝑉 .

The proof follows from applying the Lipschitz continuous property on 𝑔 𝑙 and 𝑔 ~ 𝑙 and then the triangle inequality, see Section A.3. Lemma 5.2 establishes a connection between 𝒢 0 𝑑 and 𝒢 0 , 𝑚 𝑑 , relying on the assumption that ∂ 𝑉 ~ is 𝜀 𝑚 -dense in ∂ 𝑉 . We now show under some mild conditions this assumption holds with high probability.

Proposition 5.3.

Assume { 𝐱 𝑖 ′ } 𝑖

1 𝑚 are samples drawn from the uniform distribution defined on ∂ 𝑉 . Let L ⁢ ( 𝑉 ) denote the ( 𝑑 − 1 ) -surface area of a bounded domain 𝑉 ⊂ ℝ 𝑑 and L ⁢ ( 𝑉 ) < ∞ . Let 𝐵 𝜀 𝑚 ⁢ ( 𝐱 ′ ) denote a ball of radius 𝜀 𝑚 centred on 𝐱 ′ , and let 𝜉 ⁢ ( 𝑑 )

𝜋 𝑑 / 2 / Γ ⁢ ( 𝑑 2 + 1 ) . For all 𝜀 𝑚 such that

𝜀 𝑚 ≥ ( L ⁢ ( 𝑉 ) 𝜉 ⁢ ( 𝑑 ) ⁢ [ 1 − 0.05 1 / 𝑚 ] ) 1 / 𝑑 .

(19)

we have

ℙ ⁢ ( ∂ 𝑉 ~ ⁢  is  ⁢ 𝜀 𝑚 ⁢ -dense  in  ⁢ ∂ 𝑉 )

0.95 .

For proof, see Section A.4. Equation 19 shows the relationship between 𝑚 and 𝜀 𝑚 , which corresponds to how ‘close’ ∂ 𝑉 ~ is to ∂ 𝑉 .

Remark 5.4.

Our numerical investigation (Section B.2) shows that the bound on 𝜀 𝑚 , as defined in Equation 19, is a decreasing function of 𝑚 , and is not sensitive to the value of L ⁢ ( 𝑉 ) .

Proposition 5.3 shows that Lemma 5.2 holds with high probability, which in turn enables us to show that indeed 𝒢 0 , 𝑚 𝑑 is an approximate Stein class.

Theorem 5.5.

Assume the conditions specified in Lemma 5.2 hold. Let 𝑞 be a smooth density supported on 𝑉 . For any 𝐠 ~ ∈ 𝒢 0 , 𝑚 𝑑 , then

𝔼 𝑞 ⁢ [ 𝒯 𝑞 ⁢ 𝒈 ~ ⁢ ( 𝒙 ) ]

𝑂 𝑃 ⁢ ( 𝜀 𝑚 ) .

(20)

The proof again follows from integration by parts, then applying Lemma 5.2, see Section A.5. This result paves the way for designing a new type of Stein divergence that measures differences between two distributions when their domain 𝑉 is truncated.

5.2Truncated Kernelised Stein Discrepancy (TKSD) and Density Estimation

Let 𝑞 and 𝑝 𝜽 be two smooth densities supported on 𝑉 . We can construct a Stein discrepancy measure, called the truncated Kernelised Stein Discrepancy (TKSD), given by

𝒟 TKSD ⁢ ( 𝑝 𝜽 | 𝑞 ) := sup 𝒈 ∈ 𝒢 0 , 𝑚 𝑑 𝔼 𝑞 ⁢ [ 𝒯 𝑝 𝜽 ⁢ 𝒈 ⁢ ( 𝒙 ) ] .

(21)

Similarly to classical SD and KSD, TKSD can still be intuitively thought as the maximum violation of Stein’s identity with respect to an approximate Stein class 𝒢 0 , 𝑚 𝑑 . It can be used to distinguish two distributions when their domain 𝑉 is truncated, but the boundary is not known analytically.

𝒟 TKSD ⁢ ( 𝑝 𝜽 | 𝑞 ) serves as the discrepancy measure between densities. Later, we propose to estimate a truncated density function by minimising this discrepancy.

Next, we show that there is an analytic solution to the constrained optimisation problem in Equation 21.

Theorem 5.6.

𝒟 TKSD ⁢ ( 𝑝 𝜽 | 𝑞 ) 2 can be written as

∑ 𝑙

1 𝑑 𝔼 𝒙 ∼ 𝑞 ⁢ 𝔼 𝒚 ∼ 𝑞 ⁢ [ 𝑢 𝑙 ⁢ ( 𝒙 , 𝒚 ) − 𝐯 𝑙 ⁢ ( 𝒙 ) ⊤ ⁢ ( 𝐊 ′ ) − 1 ⁢ 𝐯 𝑙 ⁢ ( 𝒚 ) ]

(22)

where 𝑢 𝑙 ⁢ ( 𝐱 , 𝐲 ) is given by Equation 7, 𝐯 𝑙 ⁢ ( 𝐳 )

𝜓 𝑝 , 𝑙 ⁢ ( 𝐳 ) ⁢ 𝛗 𝐳 , 𝐱 ′ ⊤ + ( ∂ 𝑧 𝑙 𝛗 𝐳 , 𝐱 ′ ) ⊤ , 𝛗 𝐳 , 𝐱 ′

[ 𝑘 ⁢ ( 𝐳 , 𝐱 1 ′ ) , … , 𝑘 ⁢ ( 𝐳 , 𝐱 𝑚 ′ ) ] , 𝜙 𝐱 ′

[ 𝑘 ⁢ ( 𝐱 1 ′ , ⋅ ) , … , 𝑘 ⁢ ( 𝐱 𝑚 ′ , ⋅ ) ] ⊤ and 𝐊 ′

𝜙 𝐱 ′ ⁢ 𝜙 𝐱 ′ ⊤ .

The proof relies on solving a Lagrangian dual problem, see Section A.6. This result gives a closed form loss function for 𝒟 TKSD ⁢ ( 𝑝 𝜽 | 𝑞 ) 2 , and is not straightforward to obtain since the constraints in 𝒢 0 , 𝑚 𝑑 are enforced on a finite set of points in ℝ 𝑑 . Equation 22 can be decomposed into the ‘KSD part’, given by the 𝑢 𝑙 ⁢ ( 𝒙 , 𝒚 ) term, and the ‘truncated part’, given by 𝐯 𝑙 ⁢ ( 𝒙 ) ⊤ ⁢ ( 𝐊 ′ ) − 1 ⁢ 𝐯 𝑙 ⁢ ( 𝒚 ) , which comes from solving for the Lagrangian dual parameter. Equation 22 is also linear in 𝑑 , so its evaluation cost only increases linearly with 𝑑 .

Next, we show that the TKSD can be approximated with samples from 𝑞 .

Theorem 5.7.

Let { 𝐱 𝑖 } 𝑖

1 𝑛 be a set of samples from 𝑞 ⁢ ( 𝐱 ) , then

𝒟 ^ TKSD ⁢ ( 𝑝 𝜽 | 𝑞 ) 2

2 𝑛 ⁢ ( 𝑛 − 1 ) ⁢ ∑ 𝑖

1 𝑛 ∑ 𝑗

1

𝑖 ≠ 𝑗 𝑛 ℎ ⁢ ( 𝒙 𝑖 , 𝒙 𝑗 ) ,

(23)

is an unbiased estimate of 𝒟 TKSD ⁢ ( 𝑝 𝛉 | 𝑞 ) 2 , where

ℎ ⁢ ( 𝒙 𝑖 , 𝒙 𝑗 )

∑ 𝑙

1 𝑑 𝑢 𝑙 ⁢ ( 𝒙 𝑖 , 𝒙 𝑗 ) − 𝐯 𝑙 ⁢ ( 𝒙 𝑖 ) ⊤ ⁢ ( 𝐊 ′ ) − 1 ⁢ 𝐯 𝑙 ⁢ ( 𝒙 𝑗 ) ,

(24)

assuming that 𝔼 𝐱 ∼ 𝑞 ⁢ 𝔼 𝐲 ∼ 𝑞 ⁢ [ ℎ ⁢ ( 𝐱 , 𝐲 ) 2 ] ≤ ∞ .

The proof follows directly from the definition of a 𝑈 -statistic (Serfling, 2009). Additionally, we could define a biased estimate of 𝒟 TKSD ⁢ ( 𝑝 𝜽 | 𝑞 ) 2 via a 𝑉 -statistic

𝒟 ^ TKSD ⁢ ( 𝑝 𝜽 | 𝑞 ) 2

1 𝑛 2 ⁢ ∑ 𝑖

1 𝑛 ∑ 𝑗

1 𝑛 ℎ ⁢ ( 𝒙 𝑖 , 𝒙 𝑗 ) .

(25)

The 𝑈 -statistic and 𝑉 -statistic for TKSD allow us to evaluate 𝒟 TKSD ⁢ ( 𝑝 𝜽 | 𝑞 ) 2 via 𝑛 samples from 𝑞 . In empirical experiments, the 𝑉 -statistic seems to give better performance overall compared to the 𝑈 -statistic.

Finally, we define our proposed estimator for unnormalised truncated density by minimising TKSD over the density parameter 𝜽 .

𝜽 ^ 𝑛 , 𝑚 := arg ⁢ min 𝜽 ⁡ 𝒟 ^ TKSD ⁢ ( 𝑝 𝜽 | 𝑞 ) 2 .

(26)

In the next section, we study the theoretical properties of Equation 26.

5.3Consistency Analysis

Since 𝒟 ^ TKSD ⁢ ( 𝑝 𝜽 | 𝑞 ) 2 is a function of 𝑚 , for the simplicity of the theorem, let us study Equation 26 at the limit of 𝑚 . Let 𝐿 ^ ⁢ ( 𝜽 ) := lim 𝑚 → ∞ 𝒟 ^ TKSD ⁢ ( 𝑝 𝜽 | 𝑞 ) 2 and define

𝜽 ^ 𝑛 := arg ⁢ min 𝜽 ⁡ 𝐿 ^ ⁢ ( 𝜽 ) .

We now prove that 𝜽 ^ 𝑛 converges to the true parameter under mild conditions:

Assumption 5.8 (Accurate Boundary Prediction).

Let

𝒕 := 𝔼 𝒚 [ ( 𝝋 𝒚 , 𝐱 ′ ⊤ [ ∇ 𝜽 𝜓 𝑝 , 𝑙 ( 𝒚 ) ) ⊤ ] | 𝜽

𝜽 ⋆ ] ∈ ℝ 𝑚 × dim ⁢ ( 𝜽 ) ,

𝒕 ( 𝒙 ) := 𝔼 𝒚 [ ( 𝝋 𝒚 , 𝒙 ⊤ [ ∇ 𝜽 𝜓 𝑝 , 𝑙 ( 𝒚 ) ) ⊤ ] | 𝜽

𝜽 ⋆ ] ∈ ℝ dim ⁢ ( 𝜽 ) .

Assume the following holds:

[ ∮ ∂ 𝑉 𝑞 ⁢ ( 𝒙 ) ⁢ 𝝋 𝒙 , 𝐱 ′ ⁢ ( 𝐊 ′ ) − 1 ⁢ 𝒕 ⁢ u ^ 𝑙 ⁢ ( 𝒙 ) ⁢ 𝑑 𝑠 ] 𝑖

=

[ ∮ ∂ 𝑉 𝑞 ⁢ ( 𝒙 ) ⁢ 𝒕 ⁢ ( 𝒙 ) ⁢ u ^ 𝑙 ⁢ ( 𝒙 ) ⁢ 𝑑 𝑠 ] 𝑖 + 𝑂 𝑃 ⁢ ( 𝜀 ^ 𝑚 ) ,

∀ 𝑖

∈ { 1 , … , dim ⁢ ( 𝜽 ) } , 𝑙 ∈ { 1 , … , 𝑑 }

(27)

where 𝜀 ^ 𝑚 is a positive decaying sequence with respect to 𝑚 and lim 𝑚 → ∞ 𝜀 ^ 𝑚

0 .

One can see that 𝝋 𝒙 , 𝐱 ′ ⁢ ( 𝐊 ′ ) − 1 ⁢ 𝒕 is the kernel least-square regression prediction of 𝒕 ⁢ ( 𝒙 ′ ) , for a 𝒙 ′ ∈ ∂ 𝑉 . 5.8 essentially states that the least squares ‘trained’ on our boundary samples, { 𝒙 𝑖 ′ ′ } 𝑖 ′

1 𝑚 , should be asymptotically accurate in terms of a testing error computed over a surface integral as 𝑚 increases.

Assumption 5.9.

The smallest eigenvalue of the Hessian of 𝐿 ^ ⁢ ( 𝜽 ) is lower bounded, i.e., 𝜆 min ⁢ [ ∇ 𝜽 2 𝐿 ^ ⁢ ( 𝜽 ) ] ≥ Λ min

0 with high probability.

In fact, we could make the same assumption on the population version of the objective function, and the convergence of the sample hessian matrix would guarantee Assumption 5.9 holds with high probability. To simplify our theoretical statement we stick to the simpler version.

Theorem 5.10.

Suppose there exists a unique 𝛉 ⋆ such that 𝑞

𝑝 𝛉 ⋆ , 5.8 and 5.9 hold, Then

‖ 𝜽 ^ 𝑛 − 𝜽 ⋆ ‖

𝑂 𝑃 ⁢ ( 1 𝑛 ) .

For proof, see Section A.7. This result shows, although our TKSD is an approximate version of KSD, the density estimator derived from TKSD is still a consistent estimator. We empirically verify this consistency in Section B.3.

6Experimental Results

To show the validity of our proposed method, we experiment on benchmark settings against TruncSM and an adaptation of bd-KSD for truncated density estimation. We also provide additional empirical experiments in the appendices; empirical consistency (Section B.3), a demonstration on the Gaussian mixture distribution (Section B.4), an implementation for truncated regression (Section B.5) and a investigation into the effect of the distribution of the boundary points (Section B.6).

6.1Computational Considerations

TKSD requires the selection of hyperparameters: the number of boundary points, 𝑚 , the choice of kernel function, 𝑘 , and the corresponding kernel hyperparameters. We focus on the Gaussian kernel, 𝑘 ⁢ ( 𝒙 , 𝒚 )

exp ⁡ { − ( 2 ⁢ 𝜎 2 ) − 1 ⁢ ‖ 𝒙 − 𝒚 ‖ 2 } , and the bandwidth parameter 𝜎 is chosen heuristically as the median of pairwise distances on the data matrix.

In choosing 𝑚 , there is a trade-off between accuracy and computational expense, since 𝐊 ′ in Equation 24 is an 𝑚 × 𝑚 matrix which requires inversion. In experiments, we let 𝑚 scale with 𝑑 2 . We provide more computational details of the method in Section B.8.

When the boundary’s functional form is unknown, the recommended distance functions by Xu (2022) and Liu et al. (2022) cannot be used, and instead TruncSM and bd-KSD must use approximate boundary points. This approximation to the distance function is given by

min 𝒙 ′ ∈ ∂ 𝑉 ~ ⁡ ‖ 𝒙 − 𝒙 ′ ‖ 𝛼 𝛾 ,

(28)

for each dataset point 𝒙 , where 𝛾 and 𝛼 are chosen based on the application. This may not provide an accurate approximation to the true distance function when 𝑚 is small.

6.2Density Truncated by the Boundary of the United States Figure 1:Density estimation when the truncation boundary is the border of the U.S., as described in Section 6.2. Top: example of increasing the number of boundary points 𝑚 . Bottom: across 256 seeds for each value of 𝑚 , mean estimation error with standard error bars for the mean of a 2D Gaussian, for TKSD and TruncSM as 𝑚 increases.

Let us consider the complicated boundary of the United States (U.S.). Let 𝑉 be the interior of the U.S. and let ∂ 𝑉 ~ be a set of coordinates (longitude and latitude) which define the country’s borders. The boundary of the U.S. is a highly irregular shape, and as such, there is no explicit expression of the boundary in this case. TruncSM and bd-KSD must use an approximate distance function (given by Equation 28), whereas TKSD can readily use the set of coordinates that give rise to the boundary.

The experiment is set up as follows. Let 𝝁 ⋆

[ − 115 , 35 ] and 𝚺

10 ⋅ 𝐼 𝑑 . Samples are simulated from 𝒩 ⁢ ( 𝝁 ⋆ , 𝚺 ) and we select only those which are in the interior of the U.S. until we reach 𝑛

400 points. Assuming 𝚺 is known, we estimate 𝝁 ⋆ with 𝝁 ^ using TKSD and compare it to the estimation using TruncSM. We also vary 𝑚 by uniformly sampling from the perimeter of the U.S., demonstrated in Figure 1 (top).

Figure 1 (bottom) shows the mean and standard error of the ℓ 2 estimation error between 𝝁 ⋆ and 𝝁 ^ , measured over 256 trials for each value of 𝑚 . TruncSM improves with higher values of 𝑚 as the approximate distance function increases in accuracy, whilst TKSD performs significantly better with fewer boundary points.

6.3Estimation Error and Dimensionality Figure 2:Mean estimation error across 256 seeds, with standard error bars, as dimension 𝑑 increases (left) and runtime for each method (right). The truncation domain is the ℓ 2 ball of radius 𝑑 0.53 (top) and ℓ 1 ball of radius 𝑑 (bottom).

Consider a simple experiment setup where 𝝁 𝑑 ⋆

𝟏 𝑑 ⋅ 0.5 , samples are simulated from 𝒩 ⁢ ( 𝝁 𝑑 ⋆ , 𝑰 𝑑 ) and are truncated be within the ℓ 𝑐 ball for 𝑐

1 and 𝑐

2 , each of radius 𝑟 , until we reach 𝑛

300 data points. We choose radii 𝑟

𝑑 0.53 for 𝑐

1 and 𝑟

𝑑 0.98 for 𝑐

2 , chosen so that the amount of points truncated across dimension is roughly 50% (see Section B.7 for details). We estimate 𝝁 𝑑 ⋆ with 𝝁 ^ , and measure the ℓ 2 estimation error against 𝝁 𝑑 ⋆ as 𝑑 increases. Each boundary point 𝒙 ′ ∈ ∂ 𝑉 ~ is simulated from 𝒩 ⁢ ( 𝟎 𝑑 , 𝑰 𝑑 ) , normalized by ‖ 𝒙 ′ ‖ 𝑐 , and multiplied by 𝑟 , resulting in a set of random points on the boundary.

Figure 2 shows the error and computation time for the following estimators:

•

TKSD: our method as described in Section 5, using a randomly sampled ∂ 𝑉 ~ .

•

TruncSM/bd-KSD (exact): the implementation by Liu et al. (2022)/Xu (2022) respectively, where the distance function is computed exactly using the known boundaries.

•

TruncSM/bd-KSD (approximate): the implementation by Liu et al. (2022)/Xu (2022) respectively with distance function given by Equation 28, using the same ∂ 𝑉 ~ as given to TKSD.

For the ℓ 2 case, TKSD marginally outperforms all competitors across all dimensions, at only a slight computational expense. For the ℓ 1 case, TKSD, bd-KSD and TruncSM have similar estimation errors across all dimensions. However, TruncSM (exact) and bd-KSD (exact) have an increasing computation time due to the costly evaluation of the distance function. In this implementation, we follow the advice of Liu et al. (2022), Section 7, where the distance function to the ℓ 1 ball is calculated via a closed-form expression, for which the computational complexity increases combinatorically with dimension.

TruncSM (approximate) and bd-KSD (approximate) have significantly higher estimation error than other methods across all benchmarks. TKSD is able to achieve the same level of accuracy as the exact methods, using the same finite set of boundary points, ∂ 𝑉 ~ .

7Discussion

We have proposed an alternative to the classical Stein class, called an approximate Stein class, bounded by a decreasing sequence instead of being strictly equal to zero. By maximising the KSD objective over this approximate Stein class, we have constructed a truncated density estimator based on KSD, called truncated KSD (TKSD), and shown that it is consistent. TKSD has advantages over the prior works by Xu (2022) and Liu et al. (2022), as it does not require a functional form of a boundary.

Some limitations of this method include the requirement of selecting hyperparameters, such as the kernel function 𝑘 and its associated hyperparameters, and the number of samples from the boundary, 𝑚 . Choice of 𝑚 may depend on applications. Still, a larger value is preferred when the complexity of the truncation boundary is higher, or the dimension increases. However, even with the heuristic approaches presented in this paper, TKSD provides competitive results.

In experimental results, we have shown that even though we assume no access to a functional form of the boundary, TKSD performs similarly to previous methods which require the boundary to be computed. In some scenarios, TKSD performs better than these methods, or takes less time to achieve the same result.

Reproducibility

All results in this paper can be reproduced using the GitHub repository located at https://github.com/dannyjameswilliams/tksd.

Acknowledgements

We thank all four reviewers for their insightful feedback and suggestions to improve the paper. We are particularly grateful for their recommendations of additional experiments. We would also like to thank Jake Spiteri, Jack Simons, Michael Whitehouse, Mingxuan Yi and Dom Owens, for their helpful input throughout the development of this work.

Daniel J. Williams was supported by a PhD studentship from the EPSRC Centre for Doctoral Training in Computational Statistics and Data Science.

References Barp et al. (2019) ↑ Barp, A., Briol, F.-X., Duncan, A., Girolami, M., and Mackey, L.Minimum stein discrepancy estimators.In Advances in Neural Information Processing Systems, volume 32, 2019. Boyd & Vandenberghe (2004) ↑ Boyd, S. and Vandenberghe, L.Convex optimization.Cambridge university press, 2004. Chen et al. (2011) ↑ Chen, L. H., Goldstein, L., and Shao, Q.-M.Normal approximation by Stein’s method, volume 2.Springer, 2011. Chwialkowski et al. (2016) ↑ Chwialkowski, K., Strathmann, H., and Gretton, A.A kernel test of goodness of fit.In Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pp.  2606–2615. PMLR, 2016. Gorham & Mackey (2015) ↑ Gorham, J. and Mackey, L.Measuring sample quality with stein's method.In Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015. Gorham et al. (2020) ↑ Gorham, J., Raj, A., and Mackey, L.Stochastic stein discrepancies.In Advances in Neural Information Processing Systems, volume 33, pp.  17931–17942. Curran Associates, Inc., 2020. Gutmann & Hyvärinen (2010) ↑ Gutmann, M. and Hyvärinen, A.Noise-contrastive estimation: A new estimation principle for unnormalized statistical models.In Proceedings of the 13th International Conference on Artificial Intelligence and Statistics, volume 9 of Proceedings of Machine Learning Research, pp.  297–304. PMLR, 2010. Gutmann & Hyvärinen (2012) ↑ Gutmann, M. U. and Hyvärinen, A.Noise-contrastive estimation of unnormalized statistical models, with applications to natural image statistics.Journal of Machine Learning Research, 13(11):307–361, 2012. Hyvärinen (2005) ↑ Hyvärinen, A.Estimation of non-normalized statistical models by score matching.Journal of Machine Learning Research, 6(24):695–709, 2005. Hyvärinen (2007) ↑ Hyvärinen, A.Some extensions of score matching.Computational statistics & data analysis, 51(5):2499–2512, 2007. Jitkrittum et al. (2017) ↑ Jitkrittum, W., Xu, W., Szabo, Z., Fukumizu, K., and Gretton, A.A linear-time kernel goodness-of-fit test.In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. Kalos & Whitlock (2009) ↑ Kalos, M. H. and Whitlock, P. A.Monte carlo methods.John Wiley & Sons, 2009. Kanagawa et al. (2019) ↑ Kanagawa, H., Jitkrittum, W., Mackey, L., Fukumizu, K., and Gretton, A.A kernel stein test for comparing latent variable models.arXiv preprint arXiv:1907.00586, 2019. Krishnamoorthy & Menon (2013) ↑ Krishnamoorthy, A. and Menon, D.Matrix inversion using cholesky decomposition.In 2013 signal processing: Algorithms, architectures, arrangements, and applications (SPA), pp.  70–72. IEEE, 2013. Lin et al. (2016) ↑ Lin, L., Drton, M., and Shojaie, A.Estimation of high-dimensional graphical models using regularized score matching.Electronic journal of statistics, 10(1):806, 2016. Liu et al. (2016) ↑ Liu, Q., Lee, J., and Jordan, M.A kernelized stein discrepancy for goodness-of-fit tests.In Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pp.  276–284. PMLR, 2016. Liu et al. (2022) ↑ Liu, S., Kanamori, T., and Williams, D. J.Estimating density models with truncation boundaries using score matching.Journal of Machine Learning Research, 23(186):1–38, 2022. Pang et al. (2020) ↑ Pang, T., Xu, K., Li, C., Song, Y., Ermon, S., and Zhu, J.Efficient learning of generative models via finite-difference score matching.In Advances in Neural Information Processing Systems, volume 33, pp.  19175–19188, 2020. Serfling (2009) ↑ Serfling, R. J.Approximation theorems of mathematical statistics.John Wiley & Sons, 2009. Sharrock et al. (2022) ↑ Sharrock, L., Simons, J., Liu, S., and Beaumont, M.Sequential neural score estimation: Likelihood-free inference with conditional score based diffusion models.arXiv preprint arXiv:2210.04872, 2022. Shi et al. (2021) ↑ Shi, J., Liu, C., and Mackey, L.Sampling with mirrored stein operators.arXiv preprint arXiv:2106.12506, 2021. Song & Ermon (2019) ↑ Song, Y. and Ermon, S.Generative modeling by estimating gradients of the data distribution.In Advances in Neural Information Processing Systems, volume 32, 2019. Song & Kingma (2021) ↑ Song, Y. and Kingma, D. P.How to train your energy-based models.arXiv preprint arXiv:2101.03288, 2021. Song et al. (2021) ↑ Song, Y., Sohl-Dickstein, J., Kingma, D. P., Kumar, A., Ermon, S., and Poole, B.Score-based generative modeling through stochastic differential equations.In International Conference on Learning Representations, 2021. Stein (1972) ↑ Stein, C.A bound for the error in the normal approximation to the distribution of a sum of dependent random variables.In Proceedings of the sixth Berkeley symposium on mathematical statistics and probability, volume 2: Probability theory, pp.  583–602. University of California Press, 1972. Steinwart & Christmann (2008) ↑ Steinwart, I. and Christmann, A.Support vector machines.Springer Science & Business Media, 2008. UCLA: Statistical Consulting Group (2022) ↑ UCLA: Statistical Consulting Group.Truncated regression — stata data analysis examples, 2022.URL https://stats.oarc.ucla.edu/stata/dae/truncated-regression/.Accessed March 17, 2023. Williams & Liu (2022) ↑ Williams, D. J. and Liu, S.Score matching for truncated density estimation on a manifold.In Topological, Algebraic and Geometric Learning Workshops 2022, pp.  312–321. PMLR, 2022. Wu et al. (2022) ↑ Wu, S., Diao, E., Elkhalil, K., Ding, J., and Tarokh, V.Score-based hypothesis testing for unnormalized models.IEEE Access, 10:71936–71950, 2022. Xu (2022) ↑ Xu, W.Standardisation-function kernel stein discrepancy: A unifying view on kernel stein discrepancy tests for goodness-of-fit.In International Conference on Artificial Intelligence and Statistics, pp.  1575–1597. PMLR, 2022. Xu & Matsuda (2021) ↑ Xu, W. and Matsuda, T.Interpretable stein goodness-of-fit tests on riemannian manifold.In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp.  11502–11513. PMLR, 2021. Yang et al. (2018) ↑ Yang, J., Liu, Q., Rao, V., and Neville, J.Goodness-of-fit testing for discrete distributions via stein discrepancy.In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp.  5561–5570. PMLR, 2018. Yu et al. (2016) ↑ Yu, M., Kolar, M., and Gupta, V.Statistical inference for pairwise graphical models using score matching.In Advances in Neural Information Processing Systems, volume 29, 2016. Yu et al. (2019) ↑ Yu, S., Drton, M., and Shojaie, A.Generalized score matching for non-negative data.Journal of Machine Learning Research, 20(76):1–70, 2019. Yu et al. (2021) ↑ Yu, S., Drton, M., and Shojaie, A.Generalized score matching for general domains.Information and Inference: A Journal of the IMA, 2021. Appendix AProofs and Additional Theoretical Results A.1Latent Variable Approximate Stein Identity

Firstly, we show that the score function, 𝝍 𝑞 ⁢ ( 𝒙 ) , is given by

𝝍 𝑞 ⁢ ( 𝒙 )

∇ 𝒙 𝑞 ⁢ ( 𝒙 ) 𝑞 ⁢ ( 𝒙 )

∫ ℝ 𝑑 ∇ 𝒙 ( 𝑞 ⁢ ( 𝒙 | 𝒛 ) ⁢ 𝑞 ⁢ ( 𝒛 ) ) 𝑞 ⁢ ( 𝒙 ) ⁢ 𝑞 ⁢ ( 𝒙 | 𝒛 ) 𝑞 ⁢ ( 𝒙 | 𝒛 ) ⁢ 𝑑 𝒛

∫ ℝ 𝑑 𝑞 ⁢ ( 𝒙 | 𝒛 ) ⁢ 𝑞 ⁢ ( 𝒛 ) 𝑞 ⁢ ( 𝒙 ) ⁢ [ ∇ 𝒙 𝑞 ⁢ ( 𝒙 | 𝒛 ) 𝑞 ⁢ ( 𝒙 | 𝒛 ) ] ⁢ 𝑑 𝒛

∫ ℝ 𝑑 𝑞 ⁢ ( 𝒛 | 𝒙 ) ⁢ ∇ 𝒙 log ⁡ 𝑞 ⁢ ( 𝒙 | 𝒛 ) ⁢ 𝑑 𝒛

𝔼 𝒛 ∼ 𝑞 ⁢ ( 𝒛 | 𝒙 ) ⁢ [ 𝜓 𝑞 ⁢ ( 𝒙 | 𝒛 ) ] ,

(29)

where 𝜓 𝑞 ⁢ ( 𝒙 | 𝒛 )

∇ 𝒙 log ⁡ 𝑞 ⁢ ( 𝒙 | 𝒛 ) . To evaluate the expectation over 𝑞 ⁢ ( 𝒛 | 𝒙 ) , Kanagawa et al. (2019) recommend approximating each element with a Monte Carlo estimate

𝔼 𝒛 ∼ 𝑞 ⁢ ( 𝒛 | 𝒙 ) ⁢ [ 𝜓 𝑞 , 𝑗 ⁢ ( 𝒙 | 𝒛 ) ]

1 𝑚 ⁢ ∑ 𝑖

1 𝑚 𝜓 𝑞 , 𝑗 ⁢ ( 𝒙 | 𝒛 𝑖 ) + 𝑂 𝑃 ⁢ ( 𝜀 𝑚 ) ,

(30)

where 𝜓 𝑞 , 𝑗 ⁢ ( 𝒙 | 𝒛 )

∂ 𝑥 𝑗 log ⁡ 𝑞 ⁢ ( 𝒙 | 𝒛 ) and we assume we have access to 𝑚 samples { 𝒛 𝑖 } 𝑖

1 𝑚 ∼ 𝑞 ⁢ ( 𝒛 | 𝒙 ) , and 𝑂 𝑃 ⁢ ( 𝜀 𝑚 ) is the Monte Carlo approximation error which decreases as the number of samples on the boundary, 𝑚 , increases.

The Stein identity with this score function is written asWe show that this existing modification of Stein discrepancies give rise to an Approximate Stein Class. Suppose 𝒇 ∈ ℱ 𝑑 , where ℱ 𝑑 is a regular Stein class. Stein’s identity with the score function from Equation 29 can be written as

𝔼 𝑞 ⁢ [ 𝒯 𝑞 ⁢ 𝒇 ⁢ ( 𝒙 ) ]

𝔼 𝑞 ⁢ [ ∑ 𝑗

1 𝑑 𝜓 𝑞 , 𝑗 ⁢ ( 𝒙 ) ⁢ 𝑓 𝑗 ⁢ ( 𝒙 ) + ∂ 𝑥 𝑗 𝑓 𝑗 ⁢ ( 𝒙 ) ]

𝔼 𝑞 ⁢ [ 𝔼 𝒛 ∼ 𝑞 ⁢ ( 𝒛 | 𝒙 ) ⁢ [ 𝜓 𝑞 , 𝑗 ⁢ ( 𝒙 | 𝒛 ) ] ⁢ 𝑓 𝑗 ⁢ ( 𝒙 ) + ∂ 𝑥 𝑗 𝑓 𝑗 ⁢ ( 𝒙 ) ] .

Substituting (30) into the above gives

𝔼 𝑞 ⁢ [ 𝒯 𝑞 ⁢ 𝒇 ⁢ ( 𝒙 ) ]

𝔼 𝑞 ⁢ [ ∑ 𝑗

1 𝑑 { ( 1 𝑚 ⁢ ∑ 𝑖

1 𝑚 𝜓 𝑞 , 𝑗 ⁢ ( 𝒙 | 𝒛 𝑖 ) + 𝑂 𝑃 ⁢ ( 𝜀 𝑚 ) ) ⁢ 𝑓 𝑗 ⁢ ( 𝒙 ) + ∂ 𝑥 𝑗 𝑓 𝑗 ⁢ ( 𝒙 ) } ]

𝔼 𝑞 ⁢ [ ∑ 𝑗

1 𝑑 { 1 𝑚 ⁢ ∑ 𝑖

1 𝑚 𝜓 𝑞 , 𝑗 ⁢ ( 𝒙 | 𝒛 𝑖 ) ⁢ 𝑓 𝑗 ⁢ ( 𝒙 ) + ∂ 𝑥 𝑗 𝑓 𝑗 ⁢ ( 𝒙 ) + 𝑂 𝑃 ⁢ ( 𝜀 𝑚 ) ⁢ 𝑓 𝑗 ⁢ ( 𝒙 ) } ]

(a) 𝔼 𝑞 ⁢ [ ∑ 𝑗

1 𝑑 { 1 𝑚 ⁢ ∑ 𝑖

1 𝑚 𝜓 𝑞 , 𝑗 ⁢ ( 𝒙 | 𝒛 𝑖 ) ⁢ 𝑓 𝑗 ⁢ ( 𝒙 ) + ∂ 𝑥 𝑗 𝑓 𝑗 ⁢ ( 𝒙 ) } ] + 𝑂 𝑃 ⁢ ( 𝜀 𝑚 )

(b) 𝑂 𝑃 ⁢ ( 𝜀 𝑚 ) ,

where equality (a) follows from the fact that the error in the Monte Carlo approximation is accounted for by the 𝑂 𝑃 ⁢ ( 𝜀 𝑚 ) term, and equality (b) follows by definition of ℱ 𝑑 being a Stein class. Therefore, 𝔼 𝑞 ⁢ [ 𝒯 𝑞 ⁢ 𝒇 ⁢ ( 𝒙 ) ]

𝑂 𝑃 ⁢ ( 𝜀 𝑚 ) , and this latent variable modification uses an Approximate Stein Class.

A.2Proof of Lemma 5.1

Let 𝒈 ∈ 𝒢 0 𝑑 . Begin by writing the expectation as an integral,

𝔼 𝑞 ⁢ [ 𝒯 𝑞 ⁢ 𝒈 ⁢ ( 𝒙 ) ]

∫ 𝑉 𝑞 ⁢ ( 𝒙 ) ⁢ 𝒯 𝑞 ⁢ 𝒈 ⁢ ( 𝒙 ) ⁢ 𝑑 𝒙

∑ 𝑙

1 𝑑 ∫ 𝑉 𝑞 ⁢ ( 𝒙 ) ⁢ ∂ 𝑥 𝑙 log ⁡ 𝑞 ⁢ ( 𝒙 ) ⁢ 𝑔 𝑙 ⁢ ( 𝒙 ) + ∂ 𝑥 𝑙 𝑔 𝑙 ⁢ ( 𝒙 ) ⁢ 𝑑 ⁢ 𝒙

∑ 𝑙

1 𝑑 ∫ 𝑉 ∂ 𝑥 𝑙 𝑞 ⁢ ( 𝒙 ) ⁢ 𝑔 𝑙 ⁢ ( 𝒙 ) + ∂ 𝑥 𝑙 𝑔 𝑙 ⁢ ( 𝒙 ) ⁢ 𝑑 ⁢ 𝒙 .

This can be expanded by integration by parts,

∑ 𝑙

1 𝑑 ∫ 𝑉 ∂ 𝑥 𝑙 𝑞 ⁢ ( 𝒙 ) ⁢ 𝑔 𝑙 ⁢ ( 𝒙 ) + ∂ 𝑥 𝑙 𝑔 𝑙 ⁢ ( 𝒙 ) ⁢ 𝑑 ⁢ 𝒙

∑ 𝑙

1 𝑑 ∮ ∂ 𝑉 𝑞 ⁢ ( 𝒙 ) ⁢ 𝑔 𝑙 ⁢ ( 𝒙 ) ⁢ u ^ 𝑙 ⁢ ( 𝒙 ) ⁢ 𝑑 𝑠 + ∑ 𝑙

1 𝑑 ∫ 𝑉 𝑞 ⁢ ( 𝒙 ) ⁢ ( ∂ 𝑥 𝑙 𝑔 𝑙 ⁢ ( 𝒙 ) − ∂ 𝑥 𝑙 𝑔 𝑙 ⁢ ( 𝒙 ) ) ⁢ 𝑑 𝒙

∑ 𝑙

1 𝑑 ∮ ∂ 𝑉 𝑞 ⁢ ( 𝒙 ) ⁢ 𝑔 𝑙 ⁢ ( 𝒙 ) ⁢ u ^ 𝑙 ⁢ ( 𝒙 ) ⁢ 𝑑 𝑠

0 ,

where the final equality comes from all evaluations 𝑔 𝑙 ⁢ ( 𝒙 ′ )

0 ⁢ ∀ 𝒙 ′ ∈ ∂ 𝑉 .

A.3Proof of Lemma 5.2.

Let 𝒈 ∈ 𝒢 0 𝑑 and 𝒈 ~ ∈ 𝒢 0 , 𝑚 𝑑 . First note that 𝒈 and 𝒈 ~ agree on ∂ 𝑉 ~ , i.e.

𝑔 𝑙 ⁢ ( 𝒙 ~ ′ )

𝑔 ~ 𝑙 ⁢ ( 𝒙 ~ ′ ) , ∀ 𝑙

1 , … , 𝑑

(31)

for all 𝒙 ~ ′ ∈ ∂ 𝑉 ~ , since all 𝒙 ~ ′ are elements of ∂ 𝑉 also, as ∂ 𝑉 ~ ⊂ ∂ 𝑉 . First, we note that since 𝑔 𝑙 and 𝑔 ~ 𝑙 are both Lipschitz continuous, then

| 𝑔 𝑙 ⁢ ( 𝒙 ′ ) − 𝑔 𝑙 ⁢ ( 𝒙 ~ ′ ) |

≤ 𝐶 1 ⁢ ‖ 𝒙 ′ − 𝒙 ~ ′ ‖ ≤ 𝐶 1 ⁢ 𝜀 𝑚

(32)

| 𝑔 ~ 𝑙 ⁢ ( 𝒙 ~ ′ ) − 𝑔 ~ 𝑙 ⁢ ( 𝒙 ′ ) |

≤ 𝐶 2 ⁢ ‖ 𝒙 ′ − 𝒙 ~ ′ ‖ ≤ 𝐶 2 ⁢ 𝜀 𝑚 ,

(33)

where ‖ 𝒙 ′ − 𝒙 ~ ′ ‖ ≤ 𝜀 𝑚 . This follows under the assumption that ∂ 𝑉 ~ is 𝜀 𝑚 -dense in ∂ 𝑉 , therefore the distance ‖ 𝒙 ′ − 𝒙 ~ ′ ‖ is at most 𝜀 𝑚 .

We seek to quantify

| 𝑔 𝑙 ⁢ ( 𝒙 ′ ) − 𝑔 ~ 𝑙 ⁢ ( 𝒙 ′ ) | ,

which is how far apart the ‘approximate’ 𝑔 ~ 𝑙 is from the ‘true’ 𝑔 𝑙 for any point 𝒙 ′ ∈ ∂ 𝑉 . Note that this includes points that are not in ∂ 𝑉 ~ . We let

𝑔 𝑙 ⁢ ( 𝒙 ′ ) − 𝑔 ~ 𝑙 ⁢ ( 𝒙 ′ )

( 𝑔 𝑙 ⁢ ( 𝒙 ′ ) − 𝑔 ~ 𝑙 ⁢ ( 𝒙 ′ ) ) + ( 𝑔 𝑙 ⁢ ( 𝒙 ~ ′ ) − 𝑔 𝑙 ⁢ ( 𝒙 ~ ′ ) ) + ( 𝑔 ~ 𝑙 ⁢ ( 𝒙 ~ ′ ) − 𝑔 ~ 𝑙 ⁢ ( 𝒙 ~ ′ ) ) ,

and by (31),

𝑔 𝑙 ⁢ ( 𝒙 ′ ) − 𝑔 ~ 𝑙 ⁢ ( 𝒙 ′ )

( 𝑔 𝑙 ⁢ ( 𝒙 ′ ) − 𝑔 ~ 𝑙 ⁢ ( 𝒙 ′ ) ) − 𝑔 𝑙 ⁢ ( 𝒙 ~ ′ ) + 𝑔 ~ 𝑙 ⁢ ( 𝒙 ~ ′ )

( 𝑔 𝑙 ⁢ ( 𝒙 ′ ) − 𝑔 𝑙 ⁢ ( 𝒙 ~ ′ ) ) + ( 𝑔 ~ 𝑙 ⁢ ( 𝒙 ~ ′ ) − 𝑔 ~ 𝑙 ⁢ ( 𝒙 ′ ) ) .

Using (32) and (33), we have the following inequality,

| 𝑔 𝑙 ⁢ ( 𝒙 ′ ) − 𝑔 ~ 𝑙 ⁢ ( 𝒙 ′ ) | ≤ | 𝑔 𝑙 ⁢ ( 𝒙 ′ ) − 𝑔 𝑙 ⁢ ( 𝒙 ~ ′ ) | + | 𝑔 ~ 𝑙 ⁢ ( 𝒙 ~ ′ ) − 𝑔 ~ 𝑙 ⁢ ( 𝒙 ′ ) | ≤ ( 𝐶 1 + 𝐶 2 ) ⁢ 𝜀 𝑚 ,

where the last step follows by the triangle inequality. Therefore, we have

| 𝑔 𝑙 ⁢ ( 𝒙 ′ ) − 𝑔 ~ 𝑙 ⁢ ( 𝒙 ′ ) |

𝑂 𝑃 ⁢ ( 𝜀 𝑚 )

as desired.

A.4Proof of Proposition 5.3

First, let L ⁢ ( 𝑉 ) denote the ( 𝑑 − 1 ) -surface area of a bounded domain 𝑉 ⊂ ℝ 𝑑 and L ⁢ ( 𝑉 ) < ∞ . For example, in 2D, L ⁢ ( 𝑉 ) corresponds to the line length of ∂ 𝑉 . We also define 𝐵 𝜀 𝑚 ⁢ ( 𝒙 ′ ) as the ball of radius 𝜀 𝑚 centred on 𝒙 ′ .

Before continuing to the proof, recall the definition of an 𝜀 -dense set: ∀ 𝒙 ′ ∈ ∂ 𝑉 , ∃ 𝒙 ~ ′ ∈ ∂ 𝑉 ~ such that 𝑑 ⁢ ( 𝒙 ′ , 𝒙 ~ ′ ) ≤ 𝜀 , where 𝑑 is some measure of distance. The statement 𝑑 ⁢ ( 𝒙 ′ , 𝒙 ~ ′ ) ≤ 𝜀 𝑚 is equivalent to 𝒙 ~ ′ ∈ 𝐵 𝜀 𝑚 ⁢ ( 𝒙 ′ ) . Now write that the probability that the definition of a 𝜀 𝑚 -dense set holds for ∂ 𝑉 ~ being dense in ∂ 𝑉 is equal to 0.95:

0.95

ℙ ⁢ ( ∀ 𝒙 ′ ∈ ∂ 𝑉 , ∃ 𝒙 ~ ′ ∈ ∂ 𝑉 ~ , 𝒙 ~ ′ ∈ 𝐵 𝜀 𝑚 ⁢ ( 𝒙 ′ ) )

1 − ℙ ⁢ ( ∃ 𝒙 ′ ∈ ∂ 𝑉 , ∀ 𝒙 ~ ′ ∈ ∂ 𝑉 ~ , 𝒙 ~ ′ ∉ 𝐵 𝜀 𝑚 ⁢ ( 𝒙 ′ ) )

1 − ℙ ⁢ ( ⋃ 𝒙 ′ ∈ ∂ 𝑉 ∀ 𝒙 ~ ′ ∈ ∂ 𝑉 ~ , 𝒙 ~ ′ ∉ 𝐵 𝜀 𝑚 ⁢ ( 𝒙 ′ ) ) .

Equivalently, by rearranging the above, we have

ℙ ⁢ ( ⋃ 𝒙 ′ ∈ ∂ 𝑉 ∀ 𝒙 ~ ′ ∈ ∂ 𝑉 ~ , 𝒙 ~ ′ ∉ 𝐵 𝜀 𝑚 ⁢ ( 𝒙 ′ ) )

0.05 .

This probability can be bounded as follows

0.05

ℙ ⁢ ( ⋃ 𝒙 ′ ∈ ∂ 𝑉 ∀ 𝒙 ~ ′ ∈ ∂ 𝑉 ~ , 𝒙 ~ ′ ∉ 𝐵 𝜀 𝑚 ⁢ ( 𝒙 ′ ) ) ≥ ℙ ⁢ ( ∀ 𝒙 ~ ′ ∈ ∂ 𝑉 ~ , 𝒙 ~ ′ ∉ 𝐵 𝜀 𝑚 ⁢ ( 𝒙 0 ′ ) )

where 𝒙 0 ′ is a single point in ∂ 𝑉 . This follows by basic laws of probability. Note that the probability on the right hand side can be written as

ℙ ⁢ ( ∀ 𝒙 ~ ′ ∈ ∂ 𝑉 ~ , 𝒙 ~ ′ ∉ 𝐵 𝜀 𝑚 ⁢ ( 𝒙 0 ′ ) )

ℙ ⁢ ( 𝒙 ~ 0 ′ ∉ 𝐵 𝜀 𝑚 ⁢ ( 𝒙 0 ′ ) ) 𝑚

[ 1 − ℙ ⁢ ( 𝒙 ~ 0 ′ ∈ 𝐵 𝜀 𝑚 ⁢ ( 𝒙 0 ′ ) ) ] 𝑚

[ 1 − Area ⁢ ( ∂ 𝑉 ∩ 𝐵 𝜀 𝑚 ⁢ ( 𝒙 0 ′ ) ) L ⁢ ( 𝑉 ) ] 𝑚 ≤ 0.05

(34)

where the first equality comes from all 𝒙 ~ ′ ∈ ∂ 𝑉 ~ being independently distributed. Area ⁢ ( 𝑆 ) denotes the surface area of the boundary set 𝑆 . For example, Area ⁢ ( ∂ 𝑉 )

L ⁢ ( 𝑉 ) . Therefore Area ⁢ ( ∂ 𝑉 ∩ 𝐵 𝜀 𝑚 ⁢ ( 𝒙 0 ′ ) ) represents the size of the region of ∂ 𝑉 that is inside 𝐵 𝜀 𝑚 ⁢ ( 𝒙 0 ′ ) , which will be the area of the boundary hyperplane of ∂ 𝑉 which passes through 𝐵 𝜀 𝑚 ⁢ ( 𝒙 0 ′ ) . We obtain the probability in the final equality by assuming that all 𝒙 ~ ′ are uniformly sampled from ∂ 𝑉 , so the probability is the proportion of ∂ 𝑉 inside 𝐵 𝜀 𝑚 ⁢ ( 𝒙 0 ′ ) as a ratio of the full ∂ 𝑉 . This probability exists under the assumption that L ⁢ ( 𝑉 ) < ∞ .

Next, we can rearrange Equation 34 to

Area ⁢ ( ∂ 𝑉 ∩ 𝐵 𝜀 𝑚 ⁢ ( 𝒙 0 ′ ) ) ≥ L ⁢ ( 𝑉 ) ⁢ [ 1 − 0.05 1 / 𝑚 ] .

Consider an upper bound for Area ⁢ ( ∂ 𝑉 ∩ 𝐵 𝜀 𝑚 ⁢ ( 𝒙 0 ′ ) ) given by the volume of 𝐵 𝜀 𝑚 ⁢ ( 𝒙 0 ′ ) , i.e.

Area ⁢ ( ∂ 𝑉 ∩ 𝐵 𝜀 𝑚 ⁢ ( 𝒙 0 ′ ) ) ≤ 𝜉 ⁢ ( 𝑑 ) ⁢ 𝜀 𝑚 𝑑 , 𝜉 ⁢ ( 𝑑 )

𝜋 𝑑 / 2 Γ ⁢ ( 𝑑 2 + 1 ) ,

where Γ is the Gamma function. Combining these bounds gives

𝜉 ⁢ ( 𝑑 ) ⁢ 𝜀 𝑚 𝑑 ≥ L ⁢ ( 𝑉 ) ⁢ [ 1 − 0.05 1 / 𝑚 ]

and therefore

𝜀 𝑚 ≥ ( L ⁢ ( 𝑉 ) 𝜉 ⁢ ( 𝑑 ) ⁢ [ 1 − 0.05 1 / 𝑚 ] ) 1 / 𝑑 ,

which completes the proof.

A.5Proof of Theorem 5.5

Let 𝒈 ∈ 𝒢 0 𝑑 and 𝒈 ~ ∈ 𝒢 0 , 𝑚 𝑑 . Begin with writing the expectation in its integral form,

𝔼 𝑞 ⁢ [ 𝒯 𝑞 ⁢ 𝒈 ~ ⁢ ( 𝒙 ) ]

∫ 𝑉 𝑞 ⁢ ( 𝒙 ) ⁢ [ ∑ 𝑙

1 𝑑 ∂ 𝑥 𝑙 log ⁡ 𝑞 ⁢ ( 𝒙 ) ⁢ 𝑔 ~ 𝑙 ⁢ ( 𝒙 ) + ∑ 𝑙

1 𝑑 ∂ 𝑥 𝑙 𝑔 ~ 𝑙 ⁢ ( 𝒙 ) ] ⁢ 𝑑 𝒙

∑ 𝑙

1 𝑑 ∫ 𝑉 𝑞 ⁢ ( 𝒙 ) ⁢ ∂ 𝑥 𝑙 log ⁡ 𝑞 ⁢ ( 𝒙 ) ⁢ 𝑔 ~ 𝑙 ⁢ ( 𝒙 ) ⁢ 𝑑 ⁢ 𝒙 + ∑ 𝑙

1 𝑑 ∫ 𝑉 𝑞 ⁢ ( 𝒙 ) ⁢ ∂ 𝑥 𝑙 𝑔 ~ 𝑙 ⁢ ( 𝒙 ) ⁢ 𝑑 ⁢ 𝒙

(a) ∑ 𝑙

1 𝑑 ∫ 𝑉 ∂ 𝑥 𝑙 𝑞 ⁢ ( 𝒙 ) ⁢ 𝑔 ~ 𝑙 ⁢ ( 𝒙 ) ⁢ 𝑑 ⁢ 𝒙 + ∑ 𝑙

1 𝑑 ∫ 𝑉 𝑞 ⁢ ( 𝒙 ) ⁢ ∂ 𝑥 𝑙 𝑔 ~ 𝑙 ⁢ ( 𝒙 ) ⁢ 𝑑 ⁢ 𝒙

(b) ∑ 𝑙

1 𝑑 ∮ ∂ 𝑉 𝑞 ⁢ ( 𝒙 ) ⁢ 𝑔 ~ 𝑙 ⁢ ( 𝒙 ) ⁢ u ^ 𝑙 ⁢ ( 𝒙 ) ⁢ 𝑑 𝑠 − ∑ 𝑙

1 𝑑 ∫ 𝑉 𝑞 ⁢ ( 𝒙 ) ⁢ ∂ 𝑥 𝑙 𝑔 ~ 𝑙 ⁢ ( 𝒙 ) ⁢ 𝑑 ⁢ 𝒙 + ∑ 𝑙

1 𝑑 ∫ 𝑉 𝑞 ⁢ ( 𝒙 ) ⁢ ∂ 𝑥 𝑙 𝑔 ~ 𝑙 ⁢ ( 𝒙 ) ⁢ 𝑑 ⁢ 𝒙

∑ 𝑙

1 𝑑 ∮ ∂ 𝑉 𝑞 ⁢ ( 𝒙 ) ⁢ 𝑔 ~ 𝑙 ⁢ ( 𝒙 ) ⁢ u ^ 𝑙 ⁢ ( 𝒙 ) ⁢ 𝑑 𝑠

where ∮ ∂ 𝑉 is the surface integral over the boundary ∂ 𝑉 , (a) comes from the identity that 𝑞 ⁢ ( 𝒙 ) ⁢ ∂ 𝑥 𝑙 log ⁡ 𝑞 ⁢ ( 𝒙 )

∂ 𝑥 𝑙 𝑞 ⁢ ( 𝒙 ) , and (b) is from integration by parts. Substitute 𝑔 ~ 𝑙 ⁢ ( 𝒙 )

𝑔 ~ 𝑙 ⁢ ( 𝒙 ) + 𝑔 𝑙 ⁢ ( 𝒙 ) − 𝑔 𝑙 ⁢ ( 𝒙 ) to obtain

∑ 𝑙

1 𝑑 ∮ ∂ 𝑉 𝑞 ⁢ ( 𝒙 ) ⁢ ( 𝑔 ~ 𝑙 ⁢ ( 𝒙 ) + 𝑔 𝑙 ⁢ ( 𝒙 ) − 𝑔 𝑙 ⁢ ( 𝒙 ) ) ⁢ u ^ 𝑙 ⁢ ( 𝒙 ) ⁢ 𝑑 𝑠

∑ 𝑙

1 𝑑 ∮ ∂ 𝑉 𝑞 ⁢ ( 𝒙 ) ⁢ ( 𝑔 ~ 𝑙 ⁢ ( 𝒙 ) − 𝑔 𝑙 ⁢ ( 𝒙 ) ) ⁢ u ^ 𝑙 ⁢ ( 𝒙 ) ⁢ 𝑑 𝑠 + ∑ 𝑙

1 𝑑 ∮ ∂ 𝑉 𝑞 ⁢ ( 𝒙 ) ⁢ 𝑔 𝑙 ⁢ ( 𝒙 ) ⁢ u ^ 𝑙 ⁢ ( 𝒙 ) ⁢ 𝑑 𝑠 .

By Lemma 5.2, | 𝑔 ~ 𝑙 ⁢ ( 𝒙 ′ ) − 𝑔 𝑙 ⁢ ( 𝒙 ′ ) |

𝑂 𝑃 ⁢ ( 𝜀 𝑚 ) , leaving

𝔼 𝑞 ⁢ [ 𝒯 𝑞 ⁢ 𝒈 ~ ⁢ ( 𝒙 ) ]

𝑂 𝑃 ⁢ ( 𝜀 𝑚 ) + ∑ 𝑙

1 𝑑 ∮ ∂ 𝑉 𝑞 ⁢ ( 𝒙 ) ⁢ 𝑔 𝑙 ⁢ ( 𝒙 ) ⁢ u ^ 𝑙 ⁢ ( 𝒙 ) ⁢ 𝑑 𝑠

As all evaluations of 𝑔 𝑙 ⁢ ( 𝒙 )

0 ⁢ ∀ 𝒙 ∈ ∂ 𝑉 by definition of 𝒢 0 𝑑 , the second term equals zero, leaving only

𝔼 𝑞 ⁢ [ 𝒯 𝑞 ⁢ 𝒈 ~ ⁢ ( 𝒙 ) ]

𝑂 𝑃 ⁢ ( 𝜀 𝑚 )

as desired.

A.6Proof of Theorem 5.6

Recall 𝒢 0 , 𝑚 𝑑

{ 𝒈 ∈ 𝒢 𝑑 | 𝒈 ⁢ ( 𝒙 ′ )

𝟎 ⁢ ∀ 𝒙 ′ ∈ ∂ 𝑉 ~ , ‖ 𝒈 ‖ 𝒢 𝑑 2 ≤ 1 } , where 𝒢 𝑑 is the product RKHS with 𝑑 elements, 𝒈

( 𝑔 1 , … , 𝑔 𝑑 ) , and 𝑔 𝑙 ∈ 𝒢 , ∀ 𝑙

1 , … , 𝑑 .

Begin with the definition of TKSD as defined in Equation 21,

sup 𝒈 ∈ 𝒢 0 , 𝑚 𝑑 𝔼 𝑞 ⁢ [ 𝒯 𝑝 𝜽 ⁢ 𝒈 ⁢ ( 𝒙 ) ] .

To solve this supremum analytically, we can reframe it as a constrained maximisation problem,

max 𝒈 ∈ 𝒢 𝑑

𝔼 𝑞 ⁢ [ 𝒯 𝑝 𝜽 ⁢ 𝒈 ⁢ ( 𝒙 ) ] ,

(35)

subject to	

𝑔 𝑙 ⁢ ( 𝒙 ′ )

0 ⁢ ∀ 𝒙 ′ ∈ ∂ 𝑉 ~ , ∀ 𝑙

1 , … , 𝑑

‖ 𝒈 ‖ 𝒢 𝑑 ≤ 1 ,

where the constraints in the definition for 𝒢 0 , 𝑚 𝑑 have been included as optimisation constraints, and the maximisation is now with respect to the RKHS function family 𝒢 𝑑 only. To solve this, we can formulate a Lagrangian dual function (Boyd & Vandenberghe, 2004).

inf 𝝂 ( 1 ) , … , 𝝂 ( 𝑑 ) , 𝜆

ℒ ⁢ ( 𝜽 , 𝒈 , 𝝂 ( 1 ) , … , 𝝂 ( 𝑑 ) , 𝜆 )

(36)

ℒ

ℒ ⁢ ( 𝜽 , 𝒈 , 𝝂 ( 1 ) , … , 𝝂 ( 𝑑 ) , 𝜆 ) :=
𝔼 𝑞 ⁢ [ 𝒯 𝑝 𝜽 ⁢ 𝒈 ⁢ ( 𝒙 ) ] + ∑ 𝑙

1 𝑑 ∑ 𝑖 ′

1 𝑚 𝜈 𝑖 ′ ( 𝑙 ) ⁢ 𝑔 𝑙 ⁢ ( 𝒙 𝑖 ′ ′ ) + 𝜆 ⁢ ( ‖ 𝒈 ‖ 𝒢 𝑑 2 − 1 ) ,

(37)

for 𝝂 ( 𝑙 ) ∈ ℝ 𝑚 ⁢ ∀ 𝑙 , 𝜆 ≥ 0 and ℒ is our Lagrangian. The overall optimisation problem that needs solving is given by

min 𝝂 ( 1 ) , … , 𝝂 ( 𝑑 ) , 𝜆 ⁡ max 𝒈 ∈ 𝒢 𝑑 ⁡ ℒ ⁢ ( 𝜽 , 𝒈 , 𝝂 ( 1 ) , … , 𝝂 ( 𝑑 ) , 𝜆 ) .

(38)

By solving the dual problem, Equation 38, we solve the primal problem, Equation 35. We can rewrite (37) as

ℒ

𝔼 𝑞 ⁢ [ ∑ 𝑙

1 𝑑 ∂ 𝑥 𝑙 log ⁡ 𝑝 𝜽 ⁢ ( 𝒙 ) ⁢ 𝑔 𝑙 ⁢ ( 𝒙 ) + ∂ 𝑥 𝑙 𝑔 𝑙 ⁢ ( 𝒙 ) ] + ∑ 𝑙

1 𝑑 ∑ 𝑖 ′

1 𝑚 𝜈 𝑖 ′ ( 𝑙 ) ⁢ 𝑔 𝑙 ⁢ ( 𝒙 𝑖 ′ ′ ) + 𝜆 ⁢ ( ‖ 𝒈 ‖ 𝒢 𝑑 2 − 1 ) ,

and expand evaluations of 𝑔 𝑙 ⁢ ( 𝒙 ) via the reproducing property of 𝒢 , given by 𝑔 𝑙 ⁢ ( 𝒙 )

⟨ 𝑔 𝑙 , 𝑘 ⁢ ( 𝒙 , ⋅ ) ⟩ 𝒢 , to

ℒ

𝔼 𝑞 ⁢ [ ∑ 𝑙

1 𝑑 ∂ 𝑥 𝑙 log ⁡ 𝑝 𝜽 ⁢ ( 𝒙 ) ⁢ ⟨ 𝑔 𝑙 , 𝑘 ⁢ ( 𝒙 , ⋅ ) ⟩ 𝒢 + ⟨ 𝑔 𝑙 , ∂ 𝑥 𝑙 𝑘 ⁢ ( 𝒙 , ⋅ ) ⟩ 𝒢 ] + ∑ 𝑖 ′

1 𝑚 ∑ 𝑖

1 𝑑 𝜈 𝑖 ′ ( 𝑙 ) ⁢ ⟨ 𝑔 𝑙 , 𝑘 ⁢ ( 𝒙 𝑖 ′ ′ , ⋅ ) ⟩ 𝒢 + 𝜆 ⁢ ( ∑ 𝑙

1 𝑑 ⟨ 𝑔 𝑙 , 𝑔 𝑙 ⟩ 𝒢 − 1 )

∑ 𝑙

1 𝑑 𝔼 𝑞 ⁢ [ ⟨ 𝑔 𝑙 , ∂ 𝑥 𝑙 log ⁡ 𝑝 𝜽 ⁢ ( 𝒙 ) ⁢ 𝑘 ⁢ ( 𝒙 , ⋅ ) + ∂ 𝑥 𝑙 𝑘 ⁢ ( 𝒙 , ⋅ ) + ∑ 𝑖 ′

1 𝑚 𝜈 𝑖 ′ ( 𝑙 ) ⁢ 𝑘 ⁢ ( 𝒙 𝑖 ′ ′ , ⋅ ) ⟩ 𝒢 ] + 𝜆 ⁢ ( ∑ 𝑙

1 𝑑 ⟨ 𝑔 𝑙 , 𝑔 𝑙 ⟩ 𝒢 − 1 )

∑ 𝑙

1 𝑑 ⟨ 𝑔 𝑙 , 𝔼 𝑞 ⁢ [ ∂ 𝑥 𝑙 log ⁡ 𝑝 𝜽 ⁢ ( 𝒙 ) ⁢ 𝑘 ⁢ ( 𝒙 , ⋅ ) + ∂ 𝑥 𝑙 𝑘 ⁢ ( 𝒙 , ⋅ ) ] + ∑ 𝑖 ′

1 𝑚 𝜈 𝑖 ′ ( 𝑙 ) ⁢ 𝑘 ⁢ ( 𝒙 𝑖 ′ ′ , ⋅ ) ⟩ 𝒢 + 𝜆 ⁢ ( ∑ 𝑙

1 𝑑 ⟨ 𝑔 𝑙 , 𝑔 𝑙 ⟩ 𝒢 − 1 ) .

(39)

The final equality holds provided that 𝔼 𝑞 ⁢ [ ∂ 𝑥 𝑙 log ⁡ 𝑝 𝜽 ⁢ ( 𝒙 ) ⁢ 𝑘 ⁢ ( 𝒙 , ⋅ ) + ∂ 𝑥 𝑙 𝑘 ⁢ ( 𝒙 , ⋅ ) + ∑ 𝑖 ′

1 𝑚 𝜈 𝑖 ′ ( 𝑙 ) ⁢ 𝑘 ⁢ ( 𝒙 𝑖 ′ ′ , ⋅ ) ] < ∞ , i.e. the term inside the expectation is Bochner integrable (Steinwart & Christmann, 2008). This same assumption was made in Chwialkowski et al. (2016), as we can consider ∑ 𝑖 ′

1 𝑚 𝜈 𝑖 ′ ( 𝑙 ) ⁢ 𝑘 ⁢ ( 𝒙 𝑖 ′ ′ , ⋅ ) as a constant with respect to the expectation.

We solve for each parameter via differentiation to obtain a closed form solution. Across dimensions, each 𝑔 𝑙 in (39) appears only additively to another, and so we can consider the 𝑙 -th element of the derivative, and solve the inner maximisation for each 𝑔 𝑙 to give a solution for 𝒈 . This differentiation gives

∂ ℒ ∂ 𝑔 𝑙

𝔼 𝑞 ⁢ [ ∂ 𝑥 𝑙 log ⁡ 𝑝 𝜽 ⁢ ( 𝒙 ) ⁢ 𝑘 ⁢ ( 𝒙 , ⋅ ) + ∂ 𝑥 𝑙 𝑘 ⁢ ( 𝒙 , ⋅ ) ] + ∑ 𝑖 ′

1 𝑚 𝜈 𝑖 ′ ( 𝑙 ) ⁢ 𝑘 ⁢ ( 𝒙 𝑖 ′ ′ , ⋅ ) + 2 ⁢ 𝜆 ⁢ 𝑔 𝑙

0 .

Rearranging for 𝑔 𝑙 gives the solution

𝑔 𝑙 ⋆

− 1 2 ⁢ 𝜆 ⁢ 𝔼 𝑞 ⁢ [ ∂ 𝑥 𝑙 log ⁡ 𝑝 𝜽 ⁢ ( 𝒙 ) ⁢ 𝑘 ⁢ ( 𝒙 , ⋅ ) + ∂ 𝑥 𝑙 𝑘 ⁢ ( 𝒙 , ⋅ ) ] − 1 2 ⁢ 𝜆 ⁢ ∑ 𝑖 ′

1 𝑚 𝜈 𝑖 ′ ( 𝑙 ) ⁢ 𝑘 ⁢ ( 𝒙 𝑖 ′ ′ , ⋅ )

− 𝑧 𝑙 2 ⁢ 𝜆 ,

where for convenience we have denoted 𝑧 𝑙

𝔼 𝑞 ⁢ [ ∂ 𝑥 𝑙 log ⁡ 𝑝 𝜽 ⁢ ( 𝒙 ) ⁢ 𝑘 ⁢ ( 𝒙 , ⋅ ) + ∂ 𝑥 𝑙 𝑘 ⁢ ( 𝒙 , ⋅ ) ] + ∑ 𝑖 ′

1 𝑚 𝜈 𝑖 ′ ( 𝑙 ) ⁢ 𝑘 ⁢ ( 𝒙 𝑖 ′ ′ , ⋅ ) . Substituting this back into (39) gives

ℒ ⁢ ( 𝜽 , 𝒈 ⋆ , 𝝂 ( 1 ) , … , 𝝂 ( 𝑑 ) , 𝜆 )

∑ 𝑙

1 𝑑 ⟨ − 𝑧 𝑙 2 ⁢ 𝜆 , 𝑧 𝑙 ⟩ 𝒢 + 𝜆 ⁢ ( ∑ 𝑖

1 𝑑 ⟨ − 𝑧 𝑙 2 ⁢ 𝜆 , − 𝑧 𝑙 2 ⁢ 𝜆 ⟩ 𝒢 − 1 )

∑ 𝑙

1 𝑑 1 4 ⁢ 𝜆 ⁢ ⟨ 𝑧 𝑙 , 𝑧 𝑙 ⟩ 𝒢 + 𝜆 ,

(40)

where 𝒈 ⋆

( 𝑔 1 ⋆ , … , 𝑔 𝑑 ⋆ ) . Solve for 𝜆 by differentiating

∂ ℒ ∂ 𝜆

− 1 4 ⁢ 𝜆 2 ⁢ ∑ 𝑖

1 𝑑 ⟨ 𝑧 𝑙 , 𝑧 𝑙 ⟩ 𝒢 + 1

0 .

Rearranging for 𝜆 gives 𝜆

± ∑ 𝑙

1 𝑑 ⟨ 𝑧 𝑙 , 𝑧 𝑙 ⟩ 𝒢 / 4 . Since 𝜆 ≥ 0 , we take the positive solution, giving 𝜆 ⋆

∑ 𝑙

1 𝑑 ⟨ 𝑧 𝑙 , 𝑧 𝑙 ⟩ 𝒢 / 2 . Substituting 𝜆 ⋆ into (40) gives

ℒ ⁢ ( 𝜽 , 𝒈 ⋆ , 𝝂 ( 1 ) , … , 𝝂 ( 𝑑 ) , 𝜆 ⋆ )

∑ 𝑙

1 𝑑 1 4 ⁢ 𝜆 ⋆ ⁢ ⟨ 𝑧 𝑙 , 𝑧 𝑙 ⟩ 𝒢 + 𝜆 ⋆

∑ 𝑙

1 𝑑 ⟨ 𝑧 𝑙 , 𝑧 𝑙 ⟩ 𝒢 .

(41)

To solve for the final Lagrangian parameters, 𝝂 ( 1 ) , … , 𝝂 ( 𝑑 ) , let us first introduce some notation. Denote

𝜙 𝐱 ′

[ 𝑘 ⁢ ( 𝒙 1 ′ , ⋅ ) ,

⋮ ,

𝑘 ⁢ ( 𝒙 𝑚 ′ , ⋅ ) ] , 𝝋 𝒛 , 𝐱 ′

[ 𝑘 ⁢ ( 𝒛 , 𝒙 1 ′ )
…
𝑘 ⁢ ( 𝒛 , 𝒙 𝑚 ′ ) ] , 𝐊 ′

𝜙 𝐱 ′ ⁢ 𝜙 𝐱 ′ ⊤ ,

where 𝒙 1 ′ , … , 𝒙 𝑚 ′ ∈ ∂ 𝑉 ~ . Now consider the equivalence

𝝂 ( 𝑙 ) ⋆ := arg ⁢ min 𝝂 ( 𝑙 ) ∑ 𝑙

1 𝑑 ⟨ 𝑧 𝑙 , 𝑧 𝑙 ⟩ 𝒢

arg ⁢ min 𝝂 ( 𝑙 ) ∑ 𝑙

1 𝑑 ⟨ 𝑧 𝑙 , 𝑧 𝑙 ⟩ 𝒢

arg ⁢ min 𝝂 ( 𝑙 ) ⟨ 𝑧 𝑙 , 𝑧 𝑙 ⟩ 𝒢 ,

as each 𝝂 ( 𝑙 ) is independent. By rewriting 𝑧 𝑙 as 𝑧 𝑙

𝔼 𝑞 ⁢ [ ∂ 𝑥 𝑙 log ⁡ 𝑝 𝜽 ⁢ ( 𝒙 ) ⁢ 𝑘 ⁢ ( 𝒙 , ⋅ ) + ∂ 𝑥 𝑙 𝑘 ⁢ ( 𝒙 , ⋅ ) ] + 𝝂 ( 𝑙 ) ⊤ ⁢ 𝜙 𝐱 ′ , we solve this again by differentiating,

𝑑 𝑑 ⁢ 𝝂 ( 𝑙 ) ⁢ ⟨ 𝑧 𝑙 , 𝑧 𝑙 ⟩ 𝒢

2 ⁢ ⟨ 𝑑 ⁢ 𝑧 𝑙 𝑑 ⁢ 𝝂 ( 𝑙 ) , 𝑧 𝑙 ⟩ 𝒢

2 ⁢ ⟨ 𝜙 𝐱 ′ , 𝔼 𝑞 ⁢ [ ∂ 𝑥 𝑙 log ⁡ 𝑝 𝜽 ⁢ ( 𝒙 ) ⁢ 𝑘 ⁢ ( 𝒙 , ⋅ ) + ∂ 𝑥 𝑙 𝑘 ⁢ ( 𝒙 , ⋅ ) ] + 𝝂 ( 𝑙 ) ⊤ ⁢ 𝜙 𝐱 ′ ⟩ 𝒢

2 ⁢ 𝔼 𝑞 ⁢ [ ∂ 𝑥 𝑙 log ⁡ 𝑝 𝜽 ⁢ ( 𝒙 ) ⁢ 𝝋 𝒙 , 𝐱 ′ + ∂ 𝑥 𝑙 𝝋 𝒙 , 𝐱 ′ ] + 2 ⁢ 𝝂 ( 𝑙 ) ⊤ ⁢ 𝜙 𝐱 ′ ⁢ 𝜙 𝐱 ′ ⊤

2 ⁢ 𝔼 𝑞 ⁢ [ ∂ 𝑥 𝑙 log ⁡ 𝑝 𝜽 ⁢ ( 𝒙 ) ⁢ 𝝋 𝒙 , 𝐱 ′ + ∂ 𝑥 𝑙 𝝋 𝒙 , 𝐱 ′ ] + 2 ⁢ 𝝂 ( 𝑙 ) ⊤ ⁢ 𝐊 ′ .

Setting equal to zero and rearranging gives

𝝂 ( 𝑙 ) ⋆

− ( 𝐊 ′ ) − 1 ⁢ 𝔼 𝑞 ⁢ [ ∂ 𝑥 𝑙 log ⁡ 𝑝 𝜽 ⁢ ( 𝒙 ) ⁢ 𝝋 𝒙 , 𝐱 ′ ⊤ + ( ∂ 𝑥 𝑙 𝝋 𝒙 , 𝐱 ′ ) ⊤ ] .

(42)

Before substituting back into (41), let us first square it and expand it as

ℒ 2

∑ 𝑙

1 𝑑 𝔼 𝒙 ∼ 𝑞 ⁢ 𝔼 𝒚 ∼ 𝑞 ⁢ [ 𝑢 𝑙 ⁢ ( 𝒙 , 𝒚 ) ] + ( 𝔼 𝒙 ∼ 𝑞 ⁢ [ ∂ 𝑥 𝑙 log ⁡ 𝑝 𝜽 ⁢ ( 𝒙 ) ⁢ 𝝋 𝒙 , 𝐱 ′ ⊤ + ( ∂ 𝑥 𝑙 𝝋 𝒙 , 𝐱 ′ ) ⊤ ] ) ⊤ ⁢ 𝝂 ( 𝑙 )

• 𝝂 ( 𝑙 ) ⊤ ⁢ 𝔼 𝒚 ∼ 𝑞 ⁢ [ ∂ 𝑦 𝑙 log ⁡ 𝑝 𝜽 ⁢ ( 𝒚 ) ⁢ 𝝋 𝒚 , 𝐱 ′ ⊤
• ( ∂ 𝑦 𝑙 𝝋 𝒚 , 𝐱 ′ ) ⊤ ]
• 𝝂 ( 𝑙 ) ⊤ ⁢ 𝐊 ′ ⁢ 𝝂 ( 𝑙 )

(43)

where 𝑢 𝑙 ⁢ ( 𝒙 , 𝒚 )

𝜓 𝑝 , 𝑙 ⁢ ( 𝒙 ) ⁢ 𝜓 𝑝 , 𝑙 ⁢ ( 𝒚 ) ⁢ 𝑘 ⁢ ( 𝒙 , 𝒚 ) + 𝜓 𝑝 , 𝑙 ⁢ ( 𝒙 ) ⁢ ∂ 𝑦 𝑙 𝑘 ⁢ ( 𝒙 , 𝒚 ) + 𝜓 𝑝 , 𝑙 ⁢ ( 𝒚 ) ⁢ ∂ 𝑥 𝑙 𝑘 ⁢ ( 𝒙 , 𝒚 ) + ∂ 𝑥 𝑙 ∂ 𝑦 𝑙 𝑘 ⁢ ( 𝒙 , 𝒚 ) . We can substitute 𝝂 ( 𝑙 ) ⋆ from (42) into ℒ 2 , denoting ℒ ⋆ 2 := ℒ ⁢ ( 𝜽 , 𝒈 ⋆ , 𝝂 ( 1 ) ⋆ , … , 𝝂 ( 𝑑 ) ⋆ , 𝜆 ) , giving

ℒ 2

∑ 𝑙

1 𝑑 𝔼 𝒙 ∼ 𝑞 ⁢ 𝔼 𝒚 ∼ 𝑞 ⁢ [ 𝑢 𝑙 ⁢ ( 𝒙 , 𝒚 ) ] + ( 𝔼 𝒙 ∼ 𝑞 ⁢ [ 𝜓 𝒙 , 𝑙 ⁢ 𝝋 𝒙 , 𝐱 ′ ⊤ + ( ∂ 𝑥 𝑙 𝝋 𝒙 , 𝐱 ′ ) ⊤ ] ) ⊤ ⁢ ( − ( 𝐊 ′ ) − 1 ⁢ 𝔼 𝒚 ∼ 𝑞 ⁢ [ 𝜓 𝒚 , 𝑙 ⁢ 𝝋 𝒚 , 𝐱 ′ ⊤ + ( ∂ 𝑦 𝑙 𝝋 𝒚 , 𝐱 ′ ) ⊤ ] )

• ( − ( 𝐊 ′ ) − 1 ⁢ 𝔼 𝒙 ∼ 𝑞 ⁢ [ 𝜓 𝒙 , 𝑙 ⁢ 𝝋 𝒙 , 𝐱 ′ ⊤

• ( ∂ 𝑥 𝑙 𝝋 𝒙 , 𝐱 ′ ) ⊤ ] ) ⊤ ⁢ 𝔼 𝒚 ∼ 𝑞 ⁢ [ 𝜓 𝒚 , 𝑙 ⁢ 𝝋 𝒚 , 𝐱 ′ ⊤

• ( ∂ 𝑦 𝑙 𝝋 𝒚 , 𝐱 ′ ) ⊤ ]

• ( − ( 𝐊 ′ ) − 1 ⁢ 𝔼 𝒙 ∼ 𝑞 ⁢ [ 𝜓 𝒙 , 𝑙 ⁢ 𝝋 𝒙 , 𝐱 ′ ⊤

• ( ∂ 𝑥 𝑙 𝝋 𝒙 , 𝐱 ′ ) ⊤ ] ) ⊤ ⁢ 𝐊 ′ ⁢ ( − ( 𝐊 ′ ) − 1 ⁢ 𝔼 𝒚 ∼ 𝑞 ⁢ [ 𝜓 𝒚 , 𝑙 ⁢ 𝝋 𝒚 , 𝐱 ′ ⊤

• ( ∂ 𝑦 𝑙 𝝋 𝒚 , 𝐱 ′ ) ⊤ ] ) ,

where, for brevity, we have written 𝜓 𝒙 , 𝑙

∂ 𝑥 𝑙 log ⁡ 𝑝 𝜽 ⁢ ( 𝒙 ) and 𝜓 𝒚 , 𝑙

∂ 𝑦 𝑙 log ⁡ 𝑝 𝜽 ⁢ ( 𝒚 ) . This can be further simplified to

ℒ 2

∑ 𝑙

1 𝑑 𝔼 𝒙 ∼ 𝑞 ⁢ 𝔼 𝒚 ∼ 𝑞 ⁢ [ 𝑢 𝑙 ⁢ ( 𝒙 , 𝒚 ) ] − ( 𝔼 𝒙 ∼ 𝑞 ⁢ [ 𝜓 𝒙 , 𝑙 ⁢ 𝝋 𝒙 , 𝐱 ′ ⊤ + ( ∂ 𝑥 𝑙 𝝋 𝒙 , 𝐱 ′ ) ⊤ ] ) ⊤ ⁢ ( 𝐊 ′ ) − 1 ⁢ 𝔼 𝒚 ∼ 𝑞 ⁢ [ 𝜓 𝒚 , 𝑙 ⁢ 𝝋 𝒚 , 𝐱 ′ ⊤ + ( ∂ 𝑦 𝑙 𝝋 𝒚 , 𝐱 ′ ) ⊤ ] ,

(44)

and equivalently

ℒ 2

∑ 𝑙

1 𝑑 𝔼 𝒙 ∼ 𝑞 ⁢ 𝔼 𝒚 ∼ 𝑞 ⁢ [ 𝑢 𝑙 ⁢ ( 𝒙 , 𝒚 ) − ( 𝜓 𝒙 , 𝑙 ⁢ 𝝋 𝒙 , 𝐱 ′ ⊤ + ( ∂ 𝑥 𝑙 𝝋 𝒙 , 𝐱 ′ ) ⊤ ) ⊤ ⁢ ( 𝐊 ′ ) − 1 ⁢ ( 𝜓 𝒚 , 𝑙 ⁢ 𝝋 𝒚 , 𝐱 ′ ⊤ + ( ∂ 𝑦 𝑙 𝝋 𝒚 , 𝐱 ′ ) ⊤ ) ] ,

(45)

giving the desired result.

A.7Proof of Theorem 5.10

First, we state a general result for proving the consistency of an empirical estimator of 𝜽 , which is second-order differentiable with respect to 𝜽 .

Lemma A.1.

Define the unique solution of empirical objective 𝛉 ^ := arg ⁢ min 𝛉 ⁡ 𝐿 ^ ⁢ ( 𝛉 ) and the population 𝛉 ⋆ := arg ⁢ min 𝛉 ⁡ 𝐿 ⁢ ( 𝛉 ) , where 𝐿 ⁢ ( 𝛉 ) := 𝔼 ⁢ [ 𝐿 ^ ⁢ ( 𝛉 ) ] . If 𝜆 min ⁢ [ ∇ 𝛉 2 𝐿 ^ ⁢ ( 𝛉 ) ] ≥ Λ min > 0 , ∀ 𝛉 and ‖ ∇ 𝛉 𝐿 ^ ⁢ ( 𝛉 ⋆ ) ‖

𝑂 𝑃 ⁢ ( 1 𝑛 ) , then ‖ 𝛉 ^ − 𝛉 ⋆ ‖

𝑂 𝑃 ⁢ ( 1 𝑛 ) . Here, 𝜆 min ⁢ ( 𝑀 ) is the smallest eigenvalue of a matrix 𝑀 .

Proof.

First, we define a function ℎ ⁢ ( 𝜽 ) := ⟨ 𝜽 ^ − 𝜽 ⋆ , 𝐿 ^ ⁢ ( 𝜽 ) ⟩ . Using the mean value theorem, we obtain ℎ ⁢ ( 𝜽 ^ ) − ℎ ⁢ ( 𝜽 ⋆ )

⟨ ∇ 𝜽 ℎ ⁢ ( 𝜽 ¯ ) , 𝜽 ^ − 𝜽 ⋆ ⟩ , where 𝜽 ¯ is the midpoint between 𝜽 ^ and 𝜽 ⋆ in a co-ordinate wise fashion. Therefore, due to the fact that ∇ 𝜽 𝐿 ^ ⁢ ( 𝜽 ^ )

0 ,

0 − ℎ ⁢ ( 𝜽 ⋆ )

⟨ 𝜽 ^ − 𝜽 ⋆ , ∇ 𝜽 𝐿 ^ ⁢ ( 𝜽 ⋆ ) ⟩

⟨ 𝜽 ^ − 𝜽 ⋆ , ∇ 𝜽 2 𝐿 ^ ⁢ ( 𝜽 ¯ ) ⁢ ( 𝜽 ^ − 𝜽 ⋆ ) ⟩ .

This implies the following inequality

‖ 𝜽 ^ − 𝜽 ⋆ ‖ ⁢ ‖ ∇ 𝜽 𝐿 ^ ⁢ ( 𝜽 ⋆ ) ‖ ≥ ‖ ( 𝜽 ^ − 𝜽 ⋆ ) ⊤ ⁢ ∇ 𝜽 2 𝐿 ^ ⁢ ( 𝜽 ^ ) ⁢ ( 𝜽 ^ − 𝜽 ⋆ ) ‖ ≥ 𝜆 min ⁢ ‖ ( 𝜽 ^ − 𝜽 ⋆ ) ‖ 2 .

Assume ‖ 𝜽 ^ − 𝜽 ⋆ ‖ ≠ 0 , 1 𝜆 min ⁢ ‖ ∇ 𝜽 𝐿 ^ ⁢ ( 𝜽 ⋆ ) ‖ ≥ ‖ 𝜽 ^ − 𝜽 ⋆ ‖ 2 . ∎

For the remainder, we need only to show that 𝒟 TKSD ⁢ ( 𝑝 𝜽 | 𝑞 ) 2 satisfies Lemma A.1.

Proof.

First, we need to show that

[ ∇ 𝜽 𝒟 TKSD ⁢ ( 𝑝 𝜽 | 𝑞 ) 2 | 𝜽

𝜽 ⋆ ] 𝑖

𝑂 𝑃 ⁢ ( 𝜀 ^ 𝑚 ) , ∀ 𝑖 .

(46)

For brevity let us define 𝔼 𝒙

𝔼 𝒙 ∼ 𝑞 and similarly 𝔼 𝒚

𝔼 𝒚 ∼ 𝑞 . Recall

𝒟 TKSD ⁢ ( 𝑝 𝜽 | 𝑞 ) 2

∑ 𝑙

1 𝑑 𝔼 𝒙 ⁢ 𝔼 𝒚 ⁢ [ 𝑢 𝑙 ⁢ ( 𝒙 , 𝒚 ) − 𝐯 𝑙 ⁢ ( 𝒙 ) ⊤ ⁢ ( 𝐊 ′ ) − 1 ⁢ 𝐯 𝑙 ⁢ ( 𝒚 ) ]

(47)

where

𝑢 𝑙 ⁢ ( 𝒙 , 𝒚 )

𝜓 𝑝 , 𝑙 ( 𝒙 ) 𝜓 𝑝 , 𝑙 ( 𝒚 ) 𝑘 ( 𝒙 , 𝒚 ) + 𝜓 𝑝 , 𝑙 ( 𝒙 ) ∂ 𝑦 𝑙 𝑘 ( 𝒙 , 𝒚 ) + 𝜓 𝑝 , 𝑙 ( 𝒚 ) ∂ 𝑥 𝑙 𝑘 ( 𝒙 , 𝒚 ) + ∂ 𝑥 𝑙 ∂ 𝑦 𝑙 𝒚 ) ,

𝐯 𝑙 ⁢ ( 𝒛 )

𝜓 𝑝 , 𝑙 ⁢ ( 𝒛 ) ⁢ 𝝋 𝒛 , 𝐱 ′ ⊤ + ( ∂ 𝑧 𝑙 𝝋 𝒛 , 𝐱 ′ ) ⊤ ,

𝝋 𝒛 , 𝐱 ′

[ 𝑘 ⁢ ( 𝒛 , 𝒙 1 ′ ) , … , 𝑘 ⁢ ( 𝒛 , 𝒙 𝑚 ′ ) ] , 𝜙 𝐱 ′

[ 𝑘 ⁢ ( 𝒙 1 ′ , ⋅ ) , … , 𝑘 ⁢ ( 𝒙 𝑚 ′ , ⋅ ) ] ⊤ and 𝐊 ′

𝜙 𝐱 ′ ⁢ 𝜙 𝐱 ′ ⊤ . Let us take the derivative of (47) with respect to 𝜽 . We first consider for the 𝑙 -th dimension of the sum, and then note that this will apply to all 𝑑 dimensions. Therefore consider

∇ 𝜽
𝒟 TKSD ⁢ ( 𝑝 𝜽 | 𝑞 ) 2 | 𝜽

𝜽 ⋆

∇ 𝜽 𝔼 𝒙 ⁢ 𝔼 𝒚 ⁢ [ 𝑢 𝑙 ⁢ ( 𝒙 , 𝒚 ) − 𝐯 𝑙 ⁢ ( 𝒙 ) ⊤ ⁢ ( 𝐊 ′ ) − 1 ⁢ 𝐯 𝑙 ⁢ ( 𝒚 ) ] | 𝜽

𝜽 ⋆

𝔼 𝒙 ⁢ 𝔼 𝒚 ⁢ [ ∇ 𝜽 𝑢 𝑙 ⁢ ( 𝒙 , 𝒚 ) − 𝒗 𝑙 ⁢ ( 𝒙 ) ⊤ ⁢ ( 𝐊 ′ ) − 1 ⁢ ( ∇ 𝜽 𝐯 𝑙 ⁢ ( 𝒚 ) ) − ( ∇ 𝜽 𝒗 𝑙 ⁢ ( 𝒙 ) ) ⊤ ⁢ ( 𝐊 ′ ) − 1 ⁢ 𝐯 𝑙 ⁢ ( 𝒚 ) ] | 𝜽

𝜽 ⋆ .

(48)

We begin by expanding the first term in (48):

𝔼 𝒙 ⁢ 𝔼 𝒚 ⁢ [ ∇ 𝜽 𝑢 𝑙 ⁢ ( 𝒙 , 𝒚 ) ] | 𝜽

𝜽 ⋆

𝔼 𝒙 𝔼 𝒚 [ 𝜓 𝑝 , 𝑙 ( 𝒙 ) 𝑘 ( 𝒙 , 𝒚 ) ( ∇ 𝜽 𝜓 𝑝 , 𝑙 ( 𝒚 ) ) + ( ∇ 𝜽 𝜓 𝑝 , 𝑙 ( 𝒙 ) ) 𝑘 ( 𝒙 , 𝒚 ) 𝜓 𝑝 , 𝑙 ( 𝒚 )

+ ( ∇ 𝜽 𝜓 𝑝 , 𝑙 ( 𝒙 ) ) ∂ 𝑦 𝑙 𝑘 ( 𝒙 , 𝒚 ) + ( ∇ 𝜽 𝜓 𝑝 , 𝑙 ( 𝒚 ) ) ∂ 𝑥 𝑙 𝑘 ( 𝒙 , 𝒚 ) ] | 𝜽

𝜽 ⋆ .

(49)

Now expand the first term of (49), giving

𝔼 𝒙 ⁢ 𝔼 𝒚 ⁢ [ 𝜓 𝑝 , 𝑙 ⁢ ( 𝒙 ) ⁢ 𝑘 ⁢ ( 𝒙 , 𝒚 ) ⁢ ( ∇ 𝜽 𝜓 𝑝 , 𝑙 ⁢ ( 𝒚 ) ) ] | 𝜽

𝜽 ⋆

∫ 𝑉 𝑞 ⁢ ( 𝒙 ) ⁢ 𝜓 𝑝 , 𝑙 ⁢ ( 𝒙 ) ⁢ 𝔼 𝒚 ⁢ [ 𝑘 ⁢ ( 𝒙 , 𝒚 ) ⁢ ( ∇ 𝜽 𝜓 𝑝 , 𝑙 ⁢ ( 𝒚 ) ) ] ⁢ 𝑑 𝒙 | 𝜽

𝜽 ⋆

∫ 𝑉 ∂ 𝑥 𝑙 𝑞 ⁢ ( 𝒙 ) ⁢ 𝔼 𝒚 ⁢ [ 𝑘 ⁢ ( 𝒙 , 𝒚 ) ⁢ [ ∇ 𝜽 𝜓 𝑝 , 𝑙 ⁢ ( 𝒚 ) ] | 𝜽

𝜽 ⋆ ] ⁢ 𝑑 ⁢ 𝒙

(50)

due to

𝑞 ⁢ ( 𝒛 ) ⁢ 𝜓 𝑝 , 𝑙 ⁢ ( 𝒛 ) | 𝜽

𝜽 ⋆

𝑞 ⁢ ( 𝒛 ) ⁢ ∂ 𝑦 𝑙 log ⁡ 𝑝 𝜽 ⋆ ⁢ ( 𝒛 )

𝑞 ⁢ ( 𝒛 ) ⁢ ∂ 𝑦 𝑙 𝑞 ⁢ ( 𝒛 ) 𝑞 ⁢ ( 𝒛 )

∂ 𝑦 𝑙 𝑞 ⁢ ( 𝒛 ) .

Then, via integration by parts, (50) becomes

∮ ∂ 𝑉 𝑞 ⁢ ( 𝒙 ) ⁢ 𝔼 𝒚 ⁢ [ 𝑘 ⁢ ( 𝒙 , 𝒚 ) ⁢ [ ∇ 𝜽 𝜓 𝑝 , 𝑙 ⁢ ( 𝒚 ) ] | 𝜽

𝜽 ⋆ ] ⁢ u ^ 𝑙 ⁢ ( 𝒙 ) ⁢ 𝑑 𝑠 − ∫ 𝑉 𝑞 ⁢ ( 𝒙 ) ⁢ [ ∂ 𝑥 𝑙 𝑘 ⁢ ( 𝒙 , 𝒚 ) ⁢ [ ∇ 𝜽 𝜓 𝑝 , 𝑙 ⁢ ( 𝒚 ) ] | 𝜽

𝜽 ⋆ ] .

We can expand the second term of (49) in a similar way:

( ∇ 𝜽 𝜓 𝑝 , 𝑙 ⁢ ( 𝒙 ) ) ⁢ 𝑘 ⁢ ( 𝒙 , 𝒚 ) ⁢ 𝜓 𝑝 , 𝑙 ⁢ ( 𝒚 )

∮ ∂ 𝑉 𝑞 ⁢ ( 𝒚 ) ⁢ 𝔼 𝒙 ⁢ [ [ ∇ 𝜽 𝜓 𝑝 , 𝑙 ⁢ ( 𝒙 ) ] | 𝜽

𝜽 ⋆ ⁢ 𝑘 ⁢ ( 𝒙 , 𝒚 ) ] ⁢ u ^ 𝑙 ⁢ ( 𝒚 ) ⁢ 𝑑 𝑠

− ∫ 𝑉 𝑞 ⁢ ( 𝒚 ) ⁢ [ [ ∇ 𝜽 𝜓 𝑝 , 𝑙 ⁢ ( 𝒙 ) ] | 𝜽

𝜽 ⋆ ⁢ ∂ 𝑦 𝑙 𝑘 ⁢ ( 𝒙 , 𝒚 ) ]

Both of these together, as they appear in (49), gives

𝐵 :=
∮ ∂ 𝑉 𝑞 ⁢ ( 𝒙 ) ⁢ 𝔼 𝒚 ⁢ [ 𝑘 ⁢ ( 𝒙 , 𝒚 ) ⁢ [ ∇ 𝜽 𝜓 𝑝 , 𝑙 ⁢ ( 𝒚 ) ] | 𝜽

𝜽 ⋆ ] ⁢ u ^ 𝑙 ⁢ ( 𝒙 ) ⁢ 𝑑 𝑠

• ∮ ∂ 𝑉 𝑞 ⁢ ( 𝒚 ) ⁢ 𝔼 𝒙 ⁢ [ [ ∇ 𝜽 𝜓 𝑝 , 𝑙 ⁢ ( 𝒙 ) ] | 𝜽

  𝜽 ⋆ ⁢ 𝑘 ⁢ ( 𝒙 , 𝒚 ) ] ⁢ u ^ 𝑙 ⁢ ( 𝒚 ) ⁢ 𝑑 𝑠 .

(51)

Now consider the second term in (48),

𝔼 𝒙 ⁢ 𝔼 𝒚
[ 𝒗 𝑙 ⁢ ( 𝒙 ) ⊤ ⁢ ( 𝐊 ′ ) − 1 ⁢ ( ∇ 𝜽 𝐯 𝑙 ⁢ ( 𝒚 ) ) ] | 𝜽

𝜽 ⋆

(52)

= 𝔼 𝒙 ⁢ 𝔼 𝒚 ⁢ [ ( 𝜓 𝑝 , 𝑙 ⁢ ( 𝒙 ) ⁢ 𝝋 𝒙 , 𝐱 ′ + ∂ 𝑥 𝑙 𝝋 𝒙 , 𝐱 ′ ) ⁢ ( 𝐊 ′ ) − 1 ⁢ ( 𝝋 𝒚 , 𝐱 ′ ⊤ ⁢ ( ∇ 𝜽 𝜓 𝑝 , 𝑙 ⁢ ( 𝒚 ) ) ⊤ ) ] | 𝜽

𝜽 ⋆

𝔼 𝒙 𝔼 𝒚 [ 𝜓 𝑝 , 𝑙 ( 𝒙 ) 𝝋 𝒙 , 𝐱 ′ ( 𝐊 ′ ) − 1 ( 𝝋 𝒚 , 𝐱 ′ ⊤ ( ∇ 𝜽 𝜓 𝑝 , 𝑙 ( 𝒚 ) ) ⊤ )

(53)

• ( ∂ 𝑥 𝑙 𝝋 𝒙 , 𝐱 ′ ) ( 𝐊 ′ ) − 1 ( 𝝋 𝒚 , 𝐱 ′ ⊤ ( ∇ 𝜽 𝜓 𝑝 , 𝑙 ( 𝒚 ) ) ⊤ ) ) ] | 𝜽

  𝜽 ⋆

= 𝔼 𝒙 ⁢ [ 𝜓 𝑝 , 𝑙 ⁢ ( 𝒙 ) ⁢ 𝝋 𝒙 , 𝐱 ′ ⁢ ( 𝐊 ′ ) − 1 ⁢ 𝔼 𝒚 ⁢ [ 𝝋 𝒚 , 𝐱 ′ ⊤ ⁢ ( ∇ 𝜽 𝜓 𝑝 , 𝑙 ⁢ ( 𝒚 ) ⊤ ) ] ] | 𝜽

𝜽 ⋆

+ 𝔼 𝒙 [ ( ∂ 𝑥 𝑙 𝝋 𝒙 , 𝐱 ′ ) ( 𝐊 ′ ) − 1 𝔼 𝒚 [ 𝝋 𝒚 , 𝐱 ′ ⊤ ( ∇ 𝜽 𝜓 𝑝 , 𝑙 ( 𝒚 ) ) ⊤ ) ] ] | 𝜽

𝜽 ⋆

(54)

Consider only the first term of the above,

𝔼 𝒙 ⁢ [ 𝜓 𝑝 , 𝑙 ⁢ ( 𝒙 ) ⁢ 𝝋 𝒙 , 𝐱 ′ ⁢ ( 𝐊 ′ ) − 1 ⁢ 𝔼 𝒚 ⁢ [ ( 𝝋 𝒚 , 𝐱 ′ ⊤ ⁢ ( ∇ 𝜽 𝜓 𝑝 , 𝑙 ⁢ ( 𝒚 ) ) ⊤ ) ] ] | 𝜽

𝜽 ⋆

∫ 𝑉 𝑞 ⁢ ( 𝒙 ) ⁢ 𝜓 𝑝 , 𝑙 ⁢ ( 𝒙 ) ⁢ 𝝋 𝒙 , 𝐱 ′ ⁢ ( 𝐊 ′ ) − 1 ⁢ 𝔼 𝒚 ⁢ [ 𝝋 𝒚 , 𝐱 ′ ⊤ ⁢ ( ∇ 𝜽 𝜓 𝑝 , 𝑙 ⁢ ( 𝒚 ) ) ⊤ ] ⁢ 𝑑 𝒙 | 𝜽

𝜽 ⋆

∫ 𝑉 ∂ 𝑥 𝑙 𝑞 ⁢ ( 𝒙 ) ⁢ 𝝋 𝒙 , 𝐱 ′ ⁢ ( 𝐊 ′ ) − 1 ⁢ 𝔼 𝒚 ⁢ [ 𝝋 𝒚 , 𝐱 ′ ⊤ ⁢ [ ∇ 𝜽 𝜓 𝑝 , 𝑙 ⁢ ( 𝒚 ) ⊤ ] | 𝜽

𝜽 ⋆ ] ⁢ 𝑑 ⁢ 𝒙 .

Integration by parts can be used to expand this to

∮ ∂ 𝑉 𝑞 ⁢ ( 𝒙 )
𝝋 𝒙 , 𝐱 ′ ⁢ ( 𝐊 ′ ) − 1 ⁢ 𝔼 𝒚 ⁢ [ 𝝋 𝒚 , 𝐱 ′ ⊤ ⁢ [ ∇ 𝜽 𝜓 𝑝 , 𝑙 ⁢ ( 𝒚 ) ⊤ ] | 𝜽

𝜽 ⋆ ] ⁢ u ^ 𝑙 ⁢ ( 𝒙 ) ⁢ 𝑑 ⁢ 𝑠

− ∫ 𝑉 𝑞 ⁢ ( 𝒙 ) ⁢ 𝝋 𝒙 , 𝐱 ′ ⁢ ( 𝐊 ′ ) − 1 ⁢ 𝔼 𝒚 ⁢ [ ∂ 𝑥 𝑙 𝝋 𝒚 , 𝐱 ′ ⊤ ⁢ [ ∇ 𝜽 𝜓 𝑝 , 𝑙 ⁢ ( 𝒚 ) ⊤ ] | 𝜽

𝜽 ⋆ ] ⁢ 𝜈 ⁢ ( 𝒙 ) ⁢ 𝑑 𝒙 .

(55)

5.8 indicates that we have the following equivalence (in a coordinate-wise fashion):

∮ ∂ 𝑉 𝑞 ⁢ ( 𝒙 ) ⁢ 𝝋 𝒙 , 𝐱 ′
( 𝐊 ′ ) − 1 ⁢ 𝔼 𝒚 ⁢ [ 𝝋 𝒚 , 𝐱 ′ ⊤ ⁢ [ ∇ 𝜽 𝜓 𝑝 , 𝑙 ⁢ ( 𝒚 ) ⊤ ] | 𝜽

𝜽 ⋆ ] ⁢ u ^ 𝑙 ⁢ ( 𝒙 ) ⁢ 𝑑 ⁢ 𝑠

= ∮ ∂ 𝑉 𝑞 ⁢ ( 𝒙 ) ⁢ 𝔼 𝒚 ⁢ [ 𝑘 ⁢ ( 𝒙 , 𝒚 ) ⁢ [ ∇ 𝜽 𝜓 𝑝 , 𝑙 ⁢ ( 𝒚 ) ⊤ ] | 𝜽

𝜽 ⋆ ] ⁢ u ^ 𝑙 ⁢ ( 𝒙 ) ⁢ 𝑑 𝑠 + 𝑂 𝑃 ⁢ ( 𝜀 ^ 𝑚 , 1 ) .

(56)

We interpret this as follows. If we consider 𝐱 ′ ∈ ∂ 𝑉 ~ as our training set, then our regression function is trained on the approximate set of boundary points. The surface integral denoted by ∮ ∂ 𝑉 is evaluating on all 𝒙 ∈ ∂ 𝑉 , the true boundary. Therefore the prediction based on 𝒙 ∈ ∂ 𝑉 is going to be well approximated by the regression function that is trained on 𝐱 ′ , and the approximation error, 𝜀 ^ 𝑚 , 1 , will decrease as 𝑚 , the number of training points, increases.

We can apply the same operations (from (54) onwards) to the third term in (48), which gives

𝔼 𝒙 ⁢ 𝔼 𝒚 ⁢ [ ( ∇ 𝜽 𝒗 𝑙 ⁢ ( 𝒙 ) ) ⊤ ⁢ ( 𝐊 ′ ) − 1 ⁢ 𝐯 𝑙 ⁢ ( 𝒚 ) ]

∮ ∂ 𝑉 𝑞 ⁢ ( 𝒚 ) ⁢ 𝔼 𝒙 ⁢ [ [ ∇ 𝜽 𝜓 𝑝 , 𝑙 ⁢ ( 𝒙 ) ⊤ ] | 𝜽

𝜽 ⋆ ⁢ 𝑘 ⁢ ( 𝒙 , 𝒚 ) ] ⁢ u ^ 𝑙 ⁢ ( 𝒚 ) ⁢ 𝑑 𝑠 + 𝑂 𝑃 ⁢ ( 𝜀 ^ 𝑚 , 2 ) ,

(57)

where 𝜀 ^ 𝑚 , 2 is the approximation error for the corresponding kernel regression on this term. When taking the sum, as it is in (48), (56) + (57),

∮ ∂ 𝑉 𝑞 ⁢ ( 𝒙 )
𝔼 𝒚 ⁢ [ 𝑘 ⁢ ( 𝒙 , 𝒚 ) ⁢ [ ∇ 𝜽 𝜓 𝑝 , 𝑙 ⁢ ( 𝒚 ) ⊤ ] | 𝜽

𝜽 ⋆ ] ⁢ u ^ 𝑙 ⁢ ( 𝒙 ) ⁢ 𝑑 ⁢ 𝑠 + 𝑂 𝑃 ⁢ ( 𝜀 ^ 𝑚 , 1 )

• ∮ ∂ 𝑉 𝑞 ⁢ ( 𝒚 ) ⁢ 𝔼 𝒙 ⁢ [ [ ∇ 𝜽 𝜓 𝑝 , 𝑙 ⁢ ( 𝒙 ) ⊤ ] | 𝜽

  𝜽 ⋆ ⁢ 𝑘 ⁢ ( 𝒙 , 𝒚 ) ] ⁢ u ^ 𝑙 ⁢ ( 𝒚 ) ⁢ 𝑑 𝑠

• 𝑂 𝑃 ⁢ ( 𝜀 ^ 𝑚 , 2 )

  𝐵
• 𝑂 𝑃 ⁢ ( 𝜀 ^ 𝑚 ) ,

where 𝜀 ^ 𝑚

𝜀 ^ 𝑚 , 1 + 𝜀 ^ 𝑚 , 2 . Therefore, when substituting all of (51), (56) and (57) back into (48), we have

∇ 𝜽 𝒟 TKSD ⁢ ( 𝑝 𝜽 | 𝑞 ) 2 | 𝜽

𝜽 ⋆

𝑂 𝑃 ⁢ ( 𝜀 ^ 𝑚 ) ,

where 𝜀 ^ 𝑚 is a decreasing function of 𝑚 .

Now we show 𝜽 ⋆ is the true density parameter, i.e., 𝑝 𝜽 ⋆

𝑞 . Let 𝒟 TKSD ⁢ ( 𝑝 𝜽 ⋆ | 𝑞 ) := 𝒟 TKSD ⁢ ( 𝑝 𝜽 | 𝑞 ) | 𝜽

𝜽 ⋆ . First, we show that 𝐿 ⁢ ( 𝜽 ⋆ )

0 . This is guaranteed as

𝐿 ⁢ ( 𝜽 ⋆ )

lim 𝑚 → ∞ 𝒟 TKSD ⁢ ( 𝑝 𝜽 ⋆ | 𝑞 ) 2

lim 𝑚 → ∞ { sup 𝒈 ∈ 𝒢 0 , 𝑚 𝑑 𝔼 𝑞 ⁢ [ 𝒯 𝑝 𝜽 ⋆ ⁢ 𝒈 ] } 2

lim 𝑚 → ∞ 𝑂 𝑃 ⁢ ( 𝜀 𝑚 )

0 ⁢  (with high probability) ,

for 𝒈 ∈ 𝒢 0 , 𝑚 𝑑 . The change from Stein discrepancy to 𝑂 𝑃 ⁢ ( 𝜀 𝑚 ) is guaranteed by Theorem 5.5. Since we assume that the minimiser of the population objective 𝜽 ⋆ is unique and our density model is identifiable, it shows that the unique solution of the population objective is the unique optimal parameter of the density model.

Second, we verify that ‖ ∇ 𝜽 𝐿 ^ ⁢ ( 𝜽 ⋆ ) ‖

𝑂 𝑃 ⁢ ( 1 𝑛 ) .

‖ ∇ 𝜽 𝐿 ^ ⁢ ( 𝜽 ⋆ ) ‖

∥ ∇ 𝜽 lim 𝑚 → ∞ 𝒟 ^ TKSD ( 𝑝 𝜽 ⋆ | 𝑞 ) 2 ∥

lim 𝑚 → ∞ ∥ ∇ 𝜽 𝒟 ^ TKSD ( 𝑝 𝜽 ⋆ | 𝑞 ) 2 ∥

lim 𝑚 → ∞ ∥ ∇ 𝜽 𝒟 ^ TKSD ( 𝑝 𝜽 ⋆ | 𝑞 ) 2 − ∇ 𝜽 𝒟 TKSD ( 𝑝 𝜽 ⋆ | 𝑞 ) 2 + ∇ 𝜽 𝒟 TKSD ( 𝑝 𝜽 ⋆ | 𝑞 ) 2 ∥

≤ lim 𝑚 → ∞ ( ∥ ∇ 𝜽 𝒟 ^ TKSD ( 𝑝 𝜽 ⋆ | 𝑞 ) 2 − ∇ 𝜽 𝒟 TKSD ( 𝑝 𝜽 ⋆ | 𝑞 ) 2 ∥ + ∥ ∇ 𝜽 𝒟 TKSD ( 𝑝 𝜽 ⋆ | 𝑞 ) 2 ∥ )

≤ lim 𝑚 → ∞ ( ∥ ∇ 𝜽 𝒟 ^ TKSD ( 𝑝 𝜽 ⋆ | 𝑞 ) 2 − ∇ 𝜽 𝒟 TKSD ( 𝑝 𝜽 ⋆ | 𝑞 ) 2 ∥ + 𝑂 𝑃 ( 𝜀 ^ 𝑚 ) )

≤ (a) lim 𝑚 → ∞ ( 𝑂 𝑃 ⁢ ( 1 𝑛 ) + 𝑂 𝑃 ⁢ ( 𝜀 ^ 𝑚 ) )

(58)

= (b) 𝑂 𝑃 ⁢ ( 1 𝑛 ) ,

where the inequality in (a) is due to the convergence of U-statistics (Serfling, 2009), and the equality in (b) is due to lim 𝑚 → ∞ 𝑂 𝑃 ⁢ ( 𝜀 ^ 𝑚 )

0 .

∎

We have ‖ ∇ 𝜽 𝐿 ^ ⁢ ( 𝜽 ⋆ ) ‖

𝑂 𝑃 ⁢ ( 1 𝑛 ) , and (5.9) provides 𝜆 min ⁢ [ ∇ 𝜽 2 𝐿 ^ ⁢ ( 𝜽 ) ] ≥ Λ min > 0 , then both conditions in Lemma A.1 are satisfied, and this concludes the proof of the consistency of 𝜽 ^ 𝑛 , i.e., ‖ 𝜽 ^ 𝑛 − 𝜽 ⋆ ‖

𝑂 𝑃 ⁢ ( 1 𝑛 ) .

Appendix BComputation B.1Empirical Convergence of 𝒈 ~ to 𝒈

In Lemma 5.2 we proved that under some conditions, the difference between 𝒈 ∈ 𝒢 0 𝑑 and 𝒈 ~ ∈ 𝒢 0 , 𝑚 𝑑 evaluated on 𝒙 ′ ∈ ∂ 𝑉 is bounded in probability by 𝜀 𝑚 and this probability tends to zero as 𝑚 → ∞ . In this section we aim to show that 𝒈 ~ converges to a specific function as 𝑚 increases, which we hypothesise is ‘true’ 𝒈 ∈ 𝒢 0 𝑑 .

Figure 3 demonstrates empirical convergence of 𝒈 ~ as 𝑚 increases for a given dataset. The experiment is setup as follows: we simulate points from a 𝒩 ⁢ ( 𝟎 2 , 𝑰 2 ) distribution (a unit Multivariate Normal distribution in 2D), then truncate data points to within the shape of the boundary based on location, and repeat until we acquire 𝑛

150 truncated points. For each value of 𝑚 , we minimise the TKSD objective to estimate 𝜽

𝟎 2 , and plug in the estimated 𝜽 ^ to the formula for 𝒈 ~ .

For lower values of 𝑚 , there are not enough boundary points to enforce the constraint well on 𝒈 ~ , and the approximate Stein identity has a high error, and the estimator is poor. The evaluations of 𝒈 ~ across the space do not match the 𝒈 ~ output for higher values of 𝑚 . As 𝑚 increases, 𝒈 ~ begins to converge to a particular shape, and the difference between function evaluations for 𝑚

150 and 𝑚

300 is small.

Figure 3:Contour lines of the optimal 𝑔 ~ 0 (first dimension of 𝒈 ~ ) output by TKSD across different values of 𝑚 and differently shaped truncation boundaries: the ℓ 1 ball (top), the ℓ 2 ball (middle) and a heart shape (bottom). Red points are all 𝑚 points in ∂ 𝑉 ~ and grey points are samples from the truncated dataset. Note that we plot only the first dimension of 𝒈 ~ (i.e. 𝑔 1 ), but we observe the same pattern with the second dimension. B.2Evaluating increasing values of 𝑚 in Proposition 5.3 Figure 4:Lower bound on 𝜀 𝑚 (given in (19)) against 𝑚 , the number of finite boundary points, plotted for different values of fixed dimension 𝑑 and boundary ‘size’ 𝐿 ⁢ ( 𝑉 ) , which scales quadratically.

In Figure 4 we show that 𝜀 𝑚 , as defined in Proposition 5.3, is bounded below by a decreasing function of 𝑚 . In this example, we plot the value of the lower bound in (19) against 𝑚 , the number of samples on the boundary set, and L ⁢ ( 𝑉 ) , the ( 𝑑 − 1 ) -surface area of the bounded domain 𝑉 , which can be considered as a proxy to measure the complexity of the boundary.

We let L ⁢ ( 𝑉 ) scale quadratically with dimension 𝑑 , and treat it as a constant. 𝑚 scales linearly, and measure the effect on the lower bound of 𝜀 𝑚 . As L ⁢ ( 𝑉 ) increases, the bound on 𝜀 𝑚 increases slightly. As 𝑚 increases, the bound on 𝜀 𝑚 decreases rapidly. Even at extremely high values of 𝜀 𝑚 , relatively small values of 𝑚 are required to shrink the bound. This result highlights how to choose 𝑚 in experiments - as 𝑚 increases, the ‘denseness’ of ∂ 𝑉 ~ in ∂ 𝑉 also increases, as expected. Whilst larger values of 𝑚 will always be better, there is a less pronounced effect when 𝑚 becomes significantly larger than zero. As discussed in Section B.8, larger 𝑚 comes with computational cost, and therefore this experiment shows that it may be beneficial to choose smaller values of 𝑚 . This is explored further in Section B.3.

B.3Empirical Consistency Figure 5:Left: Estimation error as 𝑛 and 𝑚 increases for TKSD only. Right: Mean estimation error for the three methods: TKSD, TruncSM and bd-KSD, with standard error bars. TKSD uses a fixed 𝑚

32 across all values of 𝑛 . Both plots report statistics over 64 seeds.

We verify that (26) is consistent estimator via empirical experiments. Note that for consistency as proven in Theorem 5.10, we require taking the limit as 𝑚 → ∞ , after which the estimator is consistent for 𝑛 . So as 𝑚 and 𝑛 increases, the estimation error decreases towards zero. We show consistency as 𝑚 and 𝑛 increase empirically in Figure 5, for a simple experiment setup, similar to the setup from Section 6.3. Data are simulated from 𝒩 ⁢ ( 𝝁 ⋆ , 𝐼 𝑑 ) , where 𝑑

2 , 𝝁 ⋆

[ 0.5 , 0.5 ] ⊤ , and 𝐼 𝑑 is known. Data are truncated to the ℓ 2 ball until we reach 𝑛 many data points (after truncation).

The aim of estimation is 𝝁 ⋆ . Across 64 trials, Figure 5 shows plots of the mean estimation error, given by ‖ 𝝁 ^ − 𝝁 ⋆ ‖ , where 𝝁 ^ is the corresponding estimate of 𝝁 ⋆ output by a given method. In the first plot (left), we show that as both 𝑛 and 𝑚 increase, the estimation error for TKSD decreases towards zero. In the second plot (right), for a fixed 𝑚 , we show that the rate of convergence as 𝑛 increases for TKSD matches that of bd-KSD and TruncSM.

B.4Gaussian Mixture Experiment Figure 6:Top: example setup for the experiment as the number of mixture modes increases from 2 to 4. Middle: estimation error as 𝑛 increases for 2 mixture modes, averaged across 256 seeds. Bottom: Estimation error as the number of mixture modes increases for a fixed 𝑛

300 , averaged across 256 seeds.

As an additional experiment to show the capability of the method, we test on a more complex problem, estimating several means of a Gaussian Mixture distribution. The estimation task is as follows. Fix 𝑑

2 and 𝑚

200 . Let the mixture modes be given as follows,

𝝁 1 ∗

[ 1.5 , 1.5 ] ⊤ , 𝝁 2 ∗

[ − 1.5 , − 1.5 ] ⊤ , 𝝁 3 ∗

[ − 1.5 , 1.5 ] ⊤ , 𝝁 4 ∗

[ 1.5 , − 1.5 ] ⊤ .

We independently simulate samples from 𝒩 ⁢ ( 𝝁 𝑖 ∗ , 𝐼 𝑑 ) , for 𝑖

1 , … , 4 , and truncate these samples to within a box with vertices at [ − 3 , − 3 ] , [ 3 , − 3 ] , [ − 3 , 3 ] and [ 3 , 3 ] until we reach a total of 𝑛 samples after truncation. Figure 6, top, shows an example of this experiment setup.

The task is to estimate 𝝁 𝑖 ∗ for all 𝑖 . To ensure a well specified experiment, we set the initial conditions of the optimisation routine as a perturbation from the true value, i.e. 𝝁 𝑖 ini

𝝁 𝑖 ∗ + 𝒛 , 𝒛 ∼ 𝒩 ⁢ ( 𝟎 , 0.5 ⋅ 𝐼 2 ) . We estimate 𝝁 with TKSD and compare it to a corresponding estimate by TruncSM across a range of different values of 𝑛 and number of mixture modes, shown in Figure 6, middle and bottom. Overall, TKSD significantly outperforms TruncSM in this experiment across all variations at the cost of runtime.

B.5Regression

We provide a further example of using TKSD to estimate the parameters of a regression problem. We provide two examples in this section, for synthetic data and for real data.

Synthetic Data

First, we simulate data in the following way:

𝑦 𝑖 ∼ 𝒩 ⁢ ( 𝜇 𝑖 , 1 ) , 𝜇 𝑖

𝛽 0 ⋆ + 𝛽 1 ⋆ ⁢ 𝑥 𝑖 , 𝑥 𝑖 ∼ Uniform ⁢ ( 0 , 1 )

where we assume knowledge of the true values, 𝛽 0 ⋆

3 and 𝛽 1 ⋆

4 . We truncate the dataset to where 𝑦 𝑖 ≥ 5 ⁢ ∀ 𝑖 , so only a portion of both 𝑦 and 𝑥 are observed. We then estimate the conditional density 𝑝 ⁢ ( 𝑦 | 𝑥 ) with TKSD via estimation of 𝜽 ⋆ := [ 𝛽 0 ⋆ , 𝛽 1 ⋆ ] ⊤ .

We obtain the log-likelihood of the Normal distribution under the estimate of 𝜽 ^ := [ 𝛽 ^ 0 , 𝛽 ^ 1 ] ⊤ output by TKSD, split across the observed dataset (within the truncation boundary) and the unobserved dataset (outside the truncation boundary). We compare these log-likelihoods to ones obtained by a naive MLE approach which does not account for truncation. As an additional measure, we calculate the unobserved error, given by

MSE ⁢ ( 𝐲 , 𝐲 ^ ) := ∑ 𝑖

1 𝑛 unobs ( 𝑦 ^ 𝑖 − 𝑦 𝑖 ) 2 , 𝑦 ^ 𝑖

𝛽 ^ 0 + 𝛽 ^ 1 ⁢ 𝑥 𝑖 ,

where 𝑛 unobs is the number of discarded data points due to truncation, and this error is calculated over these discarded data points only. This forms a measure which evaluates how well the density estimation method is predicting on unseen data points. Instead of traditional test error, it is the error on data points that have been truncated and hence no longer observed by either method.

A histogram of log-likelihoods and errors across 256 trials is given in Figure 7 (left), and an example of one such simulated regression is given in Figure 7 (top-right). The log-likelihoods for the observed points are higher for MLE, since the objective of this method is to directly maximise these likelihoods. However, on the unobserved dataset, the log-likelihoods obtained by TKSD are significantly higher than MLE. The unobserved errors are significantly smaller for TKSD, showing the improvement of TKSD over the naive approach.

Real Data: Student Test Scores

We also experiment on a real-world dataset given by UCLA: Statistical Consulting Group (2022) (Example 1). This dataset contains student test scores in a school for which the acceptance threshold is 40 out of 100, and therefore the response variable (the test scores) are truncated below by 40 and above by 100. Since no scores get close to 100, we only consider one-sided truncation at 𝑦

40 . The aim of the regression is to model the response variable, the test scores, based on a single covariate of each students’ corresponding score on a different test. Figure 7 (bottom-right) shows the plotted dataset and the regression line fit by TKSD and naive MLE. Whilst we have no true baseline value to compare to, the TKSD regression line seems to account for the truncation, whilst as expected, MLE does not.

Figure 7:Statistics from regression fit. Left:Mean squared errors only on the observed dataset (top). Log-likelihoods on the observed dataset (middle) and the unobserved dataset (bottom), both for a 𝒩 ⁢ ( 𝜇 , 1 ) distribution and over 256 trials. Right: An example of TKSD used to fit regression on the synthetic data on one trial (top) and TKSD used to fit regression on student test scores data (bottom). Fuller black points are the observed data points, after truncation, and smaller grey points are the unobserved data points that were truncated out in the data simulation process. B.6Quantifying Effect of Boundary Point Distribution

We test whether the effect of boundary point sampling distribution has an effect on the robustness of TKSD. To do so, we repeat the simple experiment setup where data are simulated as follows,

𝒙 ∼ 𝒩 ⁢ ( 𝝁 ⋆ , 𝑰 2 ) , 𝝁 ⋆

[ 1 ,

1 ] ⊤

from which we observe 𝑛

400 realisations of 𝒙 that are restricted to the unit ℓ 2 ball around the origin, and let 𝑚

30 . We use TKSD to provide an estimate 𝝁 ^ of 𝝁 ⋆ under three scenarios:

1.

Boundary points are distributed towards 𝝁 ⋆ , i.e. samples from ∂ 𝑉 ~ are closer to the centre of the dataset.

2.

Boundary points are distributed away from 𝝁 ⋆ , i.e. samples from ∂ 𝑉 ~ are closer to the edge of the dataset.

3.

Boundary points are sampled uniformly across ∂ 𝑉 .

Figure 8:Example of experiment setup for measuring the effect of the boundary point distribution. Figure 9:Frequency of estimation errors ( ‖ 𝝁 ^ − 𝝁 ⋆ ‖ ) in the simple experiment setup for the three differently distributed boundary points.

See Figure 8 for a visual representation of these three scenarios. We measure the estimation error, ‖ 𝝁 ^ − 𝝁 ⋆ ‖ , and test whether one scenario provides a lower error on average overall. Figure 9 shows the distribution of all three estimation errors across 256 trials. Scenario 1 and 3 provide comparable error distributions which are significantly smaller than the error distribution of scenario 2, implying that either the boundary needs to be covered fully, or the boundary points need to be ‘representative’ in some way, where the most significant truncation effect is.

B.7Choosing Boundary Size for Dimension Benchmarks Figure 10:Mean percentage of points which remain after truncation as dimension 𝑑 increases, where the truncation domain is a ℓ 𝑐 ball of radius 𝑑 0.98 for 𝑐

1 (left), and 𝑑 0.53 for 𝑐

2 (right).

In Section 6.3, we chose the size of the boundary to scale with 𝑑 so that roughly the same amount of data points are truncated for each value of dimension 𝑑 . The values of 𝑑 0.98 and 𝑑 0.53 for the ℓ 1 ball and ℓ 2 ball respectively were chosen via trial and error such that the percentage of points simulated from the Normal distribution remaining after truncation did not vary significantly. Figure 10 shows that with this choice of ℓ 1 and ℓ 2 ball radius, the mean percentage of points that remain after truncation remains at consistent as dimension increases in both cases.

B.8Extra Computation Details •

The inversion of 𝐊 ′ is the largest computational expense when it comes to evaluating the 𝑈 -statistic or 𝑉 -statistic ((24) and (25) respectively).

If 𝑚 < 𝑑 , which will be common as we want 𝑚 to be large, then 𝐊 ′ is rank deficient. To circumvent this issue, we invert 𝐊 ′ + 𝜖 ⁢ 𝐈 𝑚 instead, where 𝜖

0 is small. Additionally, 𝐊 ′ + 𝜖 ⁢ 𝐈 𝑚 is symmetric and positive definite, so we can exploit its Cholesky decomposition to make the inversion faster and more stable.

Overall, this inversion looks like

( 𝐊 ′ ) − 1 ≈ ( 𝐊 ′ + 𝜖 ⁢ 𝐈 𝑚 ) − 1

𝐋 − 1 ⁢ ( 𝐋 − 1 ) ⊤ ,

where 𝐋 is the corresponding lower triangular matrix from the Cholesky decomposition of 𝐊 ′ + 𝜖 ⁢ 𝐈 𝑚 . The inversion of 𝐋 , a lower triangular matrix, requires half as many operations as inverting 𝐊 + 𝜖 ⁢ 𝐈 𝑚 directly (Krishnamoorthy & Menon, 2013).

•

We also make use of methods presented in Jitkrittum et al. (2017) for fast computation when constructing all kernel matrices in Python.

Report Issue Report Issue for Selection Generated by L A T E xml Instructions for reporting errors

We are continuing to improve HTML versions of papers, and your feedback helps enhance accessibility and mobile support. To report errors in the HTML that will help us improve conversion and rendering, choose any of the methods listed below:

Click the "Report Issue" button. Open a report feedback form via keyboard, use "Ctrl + ?". Make a text selection and click the "Report Issue for Selection" button near your cursor. You can use Alt+Y to toggle on and Alt+Shift+Y to toggle off accessible reporting links at each section.

Our team has already identified the following issues. We appreciate your time reviewing and reporting rendering errors we may not have found yet. Your efforts will help us improve the HTML versions for all readers, because disability should not be a barrier to accessing research. Thank you for your continued support in championing open access for all.

Have a free development cycle? Help support accessibility at arXiv! Our collaborators at LaTeXML maintain a list of packages that need conversion, and welcome developer contributions.