Shivam Gupta<EMAIL_ADDRESS>
The University of Texas at Austin and Jasper C.H. Lee<EMAIL_ADDRESS>
University of Wisconsin-Madison and Eric Price<EMAIL_ADDRESS>
The University of Texas at Austin

# Finite-Sample Symmetric Mean Estimation
with Fisher Information Rate

###### Abstract

The mean of an unknown variance-$\sigma^{2}$ distribution $f$ can be estimated
from $n$ samples with variance $\frac{\sigma^{2}}{n}$ and nearly corresponding
subgaussian rate. When $f$ is known up to translation, this can be improved
asymptotically to $\frac{1}{n\mathcal{I}}$, where $\mathcal{I}$ is the Fisher
information of the distribution. Such an improvement is not possible for
general unknown $f$, but Stone (1975) showed that this asymptotic convergence
_is_ possible if $f$ is _symmetric_ about its mean. Stone’s bound is
asymptotic, however: the $n$ required for convergence depends in an
unspecified way on the distribution $f$ and failure probability $\delta$. In
this paper we give finite-sample guarantees for symmetric mean estimation in
terms of Fisher information. For every $f,n,\delta$ with
$n>\log\frac{1}{\delta}$, we get convergence close to a subgaussian with
variance $\frac{1}{n\mathcal{I}_{r}}$, where $\mathcal{I}_{r}$ is the
$r$-_smoothed_ Fisher information with smoothing radius $r$ that decays
polynomially in $n$. Such a bound essentially matches the finite-sample
guarantees in the known-$f$ setting.

###### keywords:

Cramér-Rao; Fisher Information; Kernel Density Estimation

##  1 Introduction

Mean estimation is a fundamental problem in statistics. For a distribution
with variance $\sigma^{2}$, the empirical mean over $n$ samples has variance
$\frac{\sigma^{2}}{n}$ and enjoys central limit behavior, asymptotically
yielding error $\sigma\sqrt{2\log\frac{1}{\delta}/n}$ with failure probability
$\delta$. Substantial work Catoni (2012); Devroye et al. (2016); Lee and
Valiant (2022b) has led to an estimator with a corresponding _finite-sample_
guarantee, achieving the same error up to a $1+o(1)$ factor.

On the other hand, consider the related problem of location estimation: if we
know the exact shape of the distribution, except for an unknown translation
parameter, the (asymptotic) estimation accuracy is characterized by the Fisher
information. More formally, suppose $x\sim f^{\lambda}(x)=f(x-\lambda)$ for
some known $f$ but some unknown parameter $\lambda$. The Fisher information of
$f$ is defined as $\mathcal{I}:=\operatorname*{\mathbb{E}}_{x\sim
f}[s(x)^{2}]$ where $s(x)$ is the “score” $s(x):=f^{\prime}(x)/f(x)$. The
_maximum likelihood estimate_ (MLE) is asymptotically normal with variance
$\frac{1}{n\mathcal{I}}$, which is at most $\frac{\sigma^{2}}{n}$; and
asymptotically, the standard Cramér-Rao bound Cramér et al. (1946); Rao (1945)
shows that this is optimal.

For example, the Laplace distribution has Fisher information
$\frac{2}{\sigma^{2}}$, and the MLE for the Laplace is the empirical median.
Thus, for the Laplace, the empirical median has half the asymptotic variance
of the empirical mean, so it needs half as many samples to achieve the same
accuracy. The Fisher information can sometimes be _much_ larger than
$1/\sigma^{2}$: consider Figure 1, a 50-50 mixture of two Gaussians
$\frac{1}{2}N(\mu_{1},\sigma_{1}^{2})+\frac{1}{2}N(\mu_{2},\sigma_{2}^{2})$
with means $\mu_{1},\mu_{2}\in[-1,1]$ and variances $\sigma_{2}^{2}\gg
1\gg\sigma_{1}^{2}$. This has variance $\Theta(\sigma_{2}^{2})$ and Fisher
information $\Theta(\frac{1}{\sigma_{1}^{2}})$. Thus, the empirical mean has
accuracy proportional to the _larger_ standard deviation, while the MLE has
accuracy proportional to the _smaller_ standard deviation. In summary, for a
_known_ $f$ at an unknown offset $\mu$, one can achieve an accuracy based on
Fisher information, which is never worse than the generic
$\sigma^{2}$-dependence but can be much better.

Figure 1: Example distributions

[The Laplace distribution has twice the Fisher information of a Gaussian with
the same variance, so it can be estimated with asymptotically half the
variance.] [When estimating a mixture of a wide and narrow Gaussian, it is
easier to estimate the mean of the narrow Gaussian. When the distribution is
known up to location, estimating this mean suffices.]

This poses a natural question: can we get Fisher-information–style
improvements for _unknown_ $f$? Unfortunately, the answer is no. In the
mixture of Gaussians example of Figure 1, in the known-distribution case we
are given $\mu_{2}-\mu_{1}$ so it suffices to estimate $\mu_{1}$. This can be
done with variance $\Theta(\frac{\sigma_{1}^{2}}{n})$. In the unknown-
distribution case we need both $\mu_{1}$ and $\mu_{2}$, and estimating
$\mu_{2}$ induces variance $\Theta(\frac{\sigma_{2}^{2}}{n})$. In fact, recent
work has shown (Dang et al., 2023) that the variance-based subgaussian error
bounds are essentially instance-optimal: for _every_ distribution $p$ of
variance $\sigma^{2}$, and any $n,\delta$ with $n\gg\log\frac{1}{\delta}$,
there exists a distribution $q$ of variance $\Theta(\sigma^{2})$ where
$|\mu_{p}-\mu_{q}|=\Omega(\sigma\sqrt{\log\frac{1}{\delta}/n})$, yet $p$ and
$q$ are not distinguishable using $n$ samples with probability $1-\delta$.

In this paper, we consider a restriction that allows for the Fisher
information benefit in mean estimation: _symmetry_. We give an estimator that,
for every _symmetric_ distribution $f$, estimates its mean with an accuracy
related to Fisher information.

#### Smoothed Fisher information.

To state our results, we need the notion of _smoothed_ Fisher information. One
issue with the aforementioned Fisher information results is that they are
asymptotic: the $n$ required for convergence depends on the distribution in a
possibly arbitrary way. As one simple example, if
$f(x)=(1-\varepsilon)N(0,1)+\varepsilon\delta_{0}$, the Fisher information is
infinite (if we see the same real-valued sample twice, that is the exact mean)
but with fewer than $1/\varepsilon$ samples we probably only see the $N(0,1)$
samples; here the best estimator is the empirical mean, with error
$N(0,\frac{1}{n})$. Thus, for finite $n$, one cannot hope for accuracy
approaching the true inverse Fisher information of a general distribution.

Recent work by Gupta et al. (2022, 2023) has given finite-$n$ bounds for the
known-distribution case in terms of the “smoothed Fisher information.” For a
distribution $f$, the $r$-smoothed Fisher information $\mathcal{I}_{r}$ is the
Fisher information of $f$ convolved with a Gaussian of variance $r^{2}$. In
these results, $r\to 0$ as $n\to\infty$, capturing the asymptotic behavior but
giving bounds that still apply when $f$ and $n$ vary together.

Figure 2 shows an example based on adding tall but narrow “teeth” to a
standard Gaussian. These teeth are useful for alignment _within_ the correct
tooth, but not very useful for alignment errors that are integer multiples of
the tooth width. As a result, if the tooth width is $w$, the optimal estimator
exhibits a phase transition in its variance, with about $\frac{1}{n}$ variance
for $n\ll\frac{1}{w^{2}}$ and $\frac{1}{n\mathcal{I}}$ variance for
$n\gg\frac{1}{w^{2}}$ (see Gupta et al. (2022)). Such a phase transition is
captured by the smoothed Fisher information, which transitions at $r\approx
w$.

Figure 2: Gaussian + Sawtooth

[In the “Gaussian+sawtooth” example, we add tall but narrow “teeth” to a
standard Gaussian. Smoothing by radius larger than the width returns the
distribution to nearly Gaussian.] [The smoothed Fisher information has a phase
transition, from a large value when $r$ is small, to the standard Gaussian’s 1
when $r$ is larger than the tooth width.]

#### Our result.

Our main theorem is the following:

######  Theorem 1.1.

Let $\eta=(\frac{\log\frac{1}{\delta}}{n})^{\frac{1}{13}}<1$, and let
$\log\frac{1}{\delta}\leq n/C$ for sufficiently large constant $C>1$. Let
$f^{*}$ be an arbitrary symmetric distribution with variance $\sigma^{2}$ and
mean $\mu$. For $\eta\sigma\leq r\leq\sigma$, we have that the output of our
estimator $\widehat{\mu}$ satisfies

$|\widehat{\mu}-\mu|\leq(1+\eta)\sqrt{\frac{2\log\frac{2}{\delta}}{n\mathcal{I}_{r}}}$

with probability $1-\delta$.

For “nice” distributions like the Laplace, $1/\mathcal{I}_{r}\approx
1/\mathcal{I}+O(r^{2})$, so Theorem 1.1 gives an error bound within
$(1+O((\frac{\log\frac{1}{\delta}}{n})^{1/13}))$ of the instance-optimal
Cramér-Rao bound. For other distributions, like the Gaussian+sawtooth example
of Figure 2, $\mathcal{I}_{r}$ exhibits a phase transition and the error does
not approach $\mathcal{I}$ until $n$ grows larger than some distribution-
dependent quantity; in the sawtooth example, $n/\log\frac{1}{\delta}$ must be
at least $O(1/w^{13})$. As discussed above, this is qualitatively correct but
with a suboptimal polynomial.

This theorem has the same form as Gupta et al. (2023), except our theorem
applies to unknown symmetric $f^{*}$ while theirs applies to known, possibly
asymmetric $f^{*}$. The differences are (I) their $\varepsilon$ is a better
polynomial, $C(\frac{\log\frac{1}{\delta}}{n})^{1/10}$; and (II) their theorem
sets $r$ in terms of the interquartile range instead of standard deviation,
and so applies to infinite-variance distributions.

Since $\frac{1}{\mathcal{I}_{r}}\leq\sigma^{2}+r^{2}$, for appropriately
chosen $r$ our bound is never more than a $(1+O(\varepsilon))$-factor worse
than the subgaussian tail with variance $\frac{\sigma^{2}}{n}$. This is
comparable to the results of Catoni (2012), although with a (slightly) weaker
convergence rate (Catoni has rate
$\varepsilon=\frac{\log\frac{1}{\delta}}{n}$). However, since Theorem 1.1
depends on the Fisher information, it can be much better: for example, it
gives a factor of $2-O(\varepsilon)$ improvement when estimating a Laplace
distribution, and variance
$\Theta\left(\frac{\min(\sigma_{1}^{2},\sigma_{2}^{2})}{n}\right)$ rather than
$\Theta\left(\frac{\max(\sigma_{1}^{2},\sigma_{2}^{2})}{n}\right)$ when $f$ is
a Gaussian mixture $\frac{1}{2}(N(\mu,\sigma_{1}^{2})+N(\mu,\sigma_{2}^{2}))$.

Theorem 1.1 assumes that we are given $r$; to choose $r$ in general, we would
want a (constant-factor) estimate of $\sigma$, which can be done if $f^{*}$
has bounded kurtosis. Avoiding this dependence is an interesting open
question.

Our estimator is based on using a small fraction of samples to construct a
kernel density estimate (KDE) of $f$, then finding a variant of the maximum
likelihood estimate (MLE). A similar approach was used in Stone (1975) to get
an asymptotic bound in terms of $\mathcal{I}$; our contribution is an
effective bound for finite $n$ that applies to any distribution,as well as
high-probability bounds.

##  2 Related Work

One dimensional mean estimation is one of the most fundamental problems in
statistics. Under the assumption of finite variance, the celebrated Central
Limit Theorem states that the distribution of the sample mean asymptotically
convergences to a Gaussian with variance $\sigma^{2}/n$. For finite-sample
performance, Nemirovsky and Yudin (1983); Jerrum et al. (1986); Alon et al.
(1999) independently invented the Median-of-Means estimator, which achieves
the same subgaussian concentration up to a constant factor. A decade ago, the
seminal work of Catoni (2012) initiated the search for a finite-sample
subgaussian estimator with a tight multiplicative constant. Subsequent
improvements by Devroye et al. (2016) and Lee and Valiant (2022b) showed how
to construct a subgaussian estimator tight up to a $1+o(1)$ multiplicative
factor.

This work, by contrast, assumes symmetry of the distribution about its mean.
Stone (1975) showed that asymptotically, the performance of mean estimation
for symmetric distributions is controlled by the Fisher information instead of
the variance. Our approach is inspired by that of Stone: construct a kernel
density estimate (KDE) of the underlying distribution, and perform maximum
likelihood estimation (MLE) based on the KDE. On the other hand, our bounds
are explicit finite-sample bounds, and characterize the performance in terms
of _smoothed_ Fisher information, with a smoothing radius $r$ that vanishes as
$n/\log\frac{1}{\delta}\to\infty$.

Fisher information also characterizes the asymptotic error in the closely-
related problem of location estimation—a parametric variant of mean
estimation—under the much stronger assumption that we know the shape of the
entire distribution up to some unknown translation van der Vaart (2000). The
recent works by Gupta et al. (2022; 2023) developed a finite-sample theory of
location estimation with error in terms of the smoothed Fisher information, up
to a $1+o(1)$ factor. Our algorithm also draws from the techniques in this
line of work. In particular, instead of finding the maximum of the empirical
log-likelihood function, they perform a single step of Newton’s method to
approximate a root of the derivative. This modification both simplifies the
algorithmic implementation and yields analysis advantages. Our algorithm and
analysis crucially leverage the same simplified view of the MLE.

Under the assumption of symmetry, therefore, our estimator is almost as good
as the best estimator for _known_ distributions. In the classical asymptotic
theory, this is referred to as an “adaptive estimator” Bickel (1982). Such
estimators are known for other semi-parametric problems, such as linear
regression with symmetric errors, estimation of the parameters of an
elliptical distribution, and two-sample comparison of a known density. A
natural question for future work is to get a finite-sample theory for these
problems.

The statistics and computer science communities have also been actively
studying the high-dimensional mean estimation problem. Lugosi and Mendelson
(2019) proposed the first subgaussian high-dimensional mean estimator up to a
multiplicative constant, but with exponential time. Hopkins (2020) and
Cherapanamjeri et al. (2019) later improved the result to take quadratic time.
A tight constant factor was achieved by Lee and Valiant (2022a) in the “very
high-dimensional” regime, but it remains an open problem to achieve a
subgaussian estimator with tight constants in general.

Recent years have seen a surge of interest in using maximum likelihood in
theoretical computer science, as a generic algorithm that can give efficient
guarantees. Such papers include, for example, profile maximum likelihood for
distribution testing and functional estimation Acharya et al. (2011, 2017);
Hao and Orlitsky (2019); Pavlichin et al. (2019); Charikar et al. (2019);
Anari et al. (2020); space-efficient streaming algorithms Pettie and Wang
(2021); and other statistical estimation problems Daskalakis et al. (2018);
Vinayak et al. (2019); Awasthi et al. (2022).

The result of this work has an “instance optimal” flavor: for each
distribution, the error bounds are phrased in terms of the (smoothed) Fisher
information. The Cramér-Rao bound shows that, even if we knew the distribution
shape, we cannot hope to do better than the Fisher information bounds.
Instance optimality and related notions have also been studied in the context
of other statistical problems, for example, identity testing Valiant and
Valiant (2017), learning discrete distributions Valiant and Valiant (2016),
mean estimation without symmetry Dang et al. (2023) and differentially-private
mean estimation Asi and Duchi (2020a, b); Huang et al. (2021).

##  3 Proof Sketch

In this section we give a very high-level overview of our proof approach; for
a more detailed quantitative overview, see Section 4. Here, we will describe
how to use $(1+O(\eta))n$ samples to get accuracy
$(1+O(\eta))\sqrt{\frac{2\log\frac{2}{\delta}}{n}}$ with probability
$1-\delta$, for $\eta=(\log\frac{1}{\delta}/n)^{1/13}$; rescaling parameters
gives the result.

Our algorithm proceeds in two phases. In the first phase, we use a small
number of samples (namely $\eta n$) to produce an initial estimate $\mu_{1}$
of $\mu$, and an approximation $\widehat{f}_{r}$ to $f_{r}$. Since $f$ is
symmetric, we can use the median of pairwise means estimator Minton and Price
(2014): $\mu_{1}=\operatorname*{median}_{i\in[\eta
n/2]}\frac{x_{2i-1}+x_{2i}}{2}$. This has subgaussian tails corresponding to
the variance of $f$:

$\varepsilon:=\mu_{1}-\mu\text{\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ satisfies\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\
}|\varepsilon|\lesssim\sqrt{\frac{\sigma^{2}\log\frac{2}{\delta}}{\eta n}}$

with probability $1-\delta$, for every $\delta>0$. In the second stage, we
want to refine this estimate to
$(1+O(\eta))\sqrt{\frac{\log\frac{2}{\delta}}{n\mathcal{I}_{r}}}$ error, which
is a small polynomial factor better (by at least $\sqrt{\eta}$, but perhaps
even better, like $(\frac{n}{\log\frac{1}{\delta}})^{0.1}$). We do so with,
essentially, one step of Newton’s method.

#### Background: known distribution case.

Suppose we knew the distribution of $f_{r}$, except for the location shift. We
consider centering the distribution at $\mu_{1}=\mu+\varepsilon$, i.e. define
$\widetilde{f}_{r}(x)=f_{r}(x-\varepsilon)$, in order to estimate
$\varepsilon$. To do so, take the score function

$\widetilde{s}_{r}(x):=\frac{\widetilde{f}^{\prime}_{r}(x)}{\widetilde{f}_{r}(x)}$

which satisfies $\widetilde{s}_{r}(x+\varepsilon)=s_{r}(x)$, where $s_{r}$ is
the score function of $f$. Therefore, by standard properties of the score
function,

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim
f_{r}}[\widetilde{s}_{r}(x+\varepsilon)]$ $\displaystyle=0$
$\displaystyle\operatorname*{\mathbb{E}}_{x\sim
f_{r}}[-\tilde{s}_{r}^{\prime}(x+\varepsilon)]=\operatorname*{\mathbb{E}}_{x\sim
f_{r}}[\widetilde{s}_{r}^{2}(x+\varepsilon)]$ $\displaystyle=\mathcal{I}_{r}.$

Since we know $\widetilde{s}_{r}$, we can take our $n$ samples $x_{i}$, add
fresh independent noise $w_{i}\sim N(0,r^{2})$ to get $x_{i}+w_{i}\sim f_{r}$,
and compute the empirical average

$\displaystyle\widehat{\operatorname*{\mathbb{E}}}[\widetilde{s}_{r}(x_{i}+w_{i})]:=\frac{1}{n}\sum_{i=1}^{n}\widetilde{s}_{r}(x_{i}+w_{i})$

One can show that this concentrates, so by a Taylor approximation

$\displaystyle\widehat{\operatorname*{\mathbb{E}}}[\widetilde{s}_{r}(x_{i}+w_{i})]\approx\operatorname*{\mathbb{E}}_{x\sim
f_{r}}[\widetilde{s}_{r}(x)]\approx\operatorname*{\mathbb{E}}_{x\sim
f_{r}}[\widetilde{s}_{r}(x+\varepsilon)-\varepsilon\tilde{s}_{r}^{\prime}(x+\varepsilon)]=-\varepsilon\operatorname*{\mathbb{E}}_{x\sim
f_{r}}[\tilde{s}_{r}^{\prime}(x+\varepsilon)]=\varepsilon\mathcal{I}_{r}$ (1)

Thus we can estimate $\mu$ as

$\widehat{\mu}:=\mu_{1}-\mathcal{I}_{r}^{-1}\widehat{\operatorname*{\mathbb{E}}}[\widetilde{s}_{r}(x_{i}+w_{i})]\approx\mu_{1}-\varepsilon=\mu.$

The new estimate $\widehat{\mu}$ has error only from the two approximations in
(1): (I) how well the empirical average score concentrates to the true
average, and (II) the Taylor approximation.

At $\varepsilon=0$, error (II) is zero and error (I) has variance
$\frac{1}{n}\text{Var}(s_{r}(x))=\frac{\mathcal{I}_{r}}{n}$. Since
$\widehat{\mu}$ rescales by $\mathcal{I}_{r}^{-1}$, this means $\widehat{\mu}$
has variance $\frac{1}{n\mathcal{I}_{r}}$ at $\varepsilon=0$—precisely the
Cramér-Rao bound we want to achieve. It was shown by Gupta et al. (2022) that
the same bound holds to within a $1+o(1)$ factor as long as $\varepsilon$ is
small relative to $r$ (namely, $|\varepsilon|\ll
r^{2}\sqrt{\mathcal{I}_{r}}$), and that the error satisfies a subgaussian tail
bound matching this variance.

#### Our setting: unknown distribution case.

The above algorithm for the known-distribution case uses knowledge of the
distribution in two ways: to compute $\widetilde{s}$, and to estimate
$\mathcal{I}_{r}$ to rescale it. But what happens if we use some function
$g(x)$ other than the score? If $g$ is antisymmetric about $\mu_{1}$, we still
have $\operatorname*{\mathbb{E}}_{x\sim f_{r}}[g(x+\varepsilon)]=0$, and so

$\displaystyle\widehat{\operatorname*{\mathbb{E}}}[g(x_{i}+w_{i})]\approx\operatorname*{\mathbb{E}}_{x\sim
f_{r}}[g(x)]\approx\operatorname*{\mathbb{E}}_{x\sim
f_{r}}[g(x+\varepsilon)-\varepsilon
g^{\prime}(x)]=-\varepsilon\operatorname*{\mathbb{E}}_{x\sim
f_{r}}[g^{\prime}(x)]$ (2)

If $g$ is reasonably smooth and $\varepsilon$ is small relative to $r$, the
Taylor approximation will be quite good, in which case

$\displaystyle\widehat{\varepsilon}:=-\frac{\widehat{\operatorname*{\mathbb{E}}}[g(x_{i}+w_{i})]}{\operatorname*{\mathbb{E}}_{x\sim
f_{r}}[g^{\prime}(x)]}$ (3)

is a low-bias estimator of $\varepsilon$. For small $\varepsilon$, we expect
this estimator to have variance close to the variance at $\varepsilon=0$,
which is

$\displaystyle\text{Var}(\widehat{\mu})\approx\frac{1}{n}\frac{\operatorname*{\mathbb{E}}_{f_{r}}[g^{2}(y)]}{\operatorname*{\mathbb{E}}_{f_{r}}[g^{\prime}(y)]^{2}}.$
(4)

One can show that this variance is at least $\frac{1}{n\mathcal{I}_{r}}$, with
minimum achieved when $g$ is the score function
$s_{r}(x)=\frac{f_{r}^{\prime}(x)}{f_{r}(x)}$, matching the Cramér-Rao bound;
see Proposition 3.1 at the end of the section. But this argument is fairly
robust: we just need $g(x)$ to be an antisymmetric function that approximates
$s_{r}$ well under these two expectations, and that is robust to perturbations
$\varepsilon\ll r$.

Our algorithm then is: using our initial set of $\eta n$ samples in the first
stage, we compute the kernel density estimate (KDE)

$\widehat{f}_{r}(x):=\frac{1}{n}\sum_{i=1}^{n}\phi\left(\frac{x-x_{i}}{r}\right)$

where $\phi(t)$ is the Gaussian density
$\phi(t)=\frac{1}{\sqrt{2\pi}}e^{-t^{2}/2}$. This has corresponding score
function
$\widehat{s}_{r}(x)=\frac{\widehat{f}^{\prime}_{r}(x)}{\widehat{f}_{r}(x)}$.
We first clip the score function to have magnitude at most
$T\approx\frac{\sqrt{\log n}}{r}$, and then antisymmetrize this score function
about $\mu_{1}$ by just copying the right side over: setting
$\widehat{s}^{sym}_{r}(x)=\widehat{s}_{r}^{clip}(2\mu_{1}-x)$ for
$x\leq\mu_{1}$. This produces the antisymmetric function
$\widehat{s}^{sym}_{r}$ we use as $g$ in the above proof outline.

The final step in our algorithm is that, in order to estimate our target via
(3), we need to approximate $\operatorname*{\mathbb{E}}_{x\sim
f_{r}}[\widehat{s}^{sym^{\prime}}(x)]$. Since $\widehat{s}^{sym}$ is close to
the true score $s_{r}(x)$, this value is close (within $1+O(\eta)$) to
$\mathcal{I}_{r}$. Thus, we can just make an estimate
$\widehat{\mathcal{I}}_{r}$ of $\mathcal{I}_{r}$ using the distribution
$\widehat{f}_{r}$.

Our sources of error are the following: (I) the empirical concentration to the
expectation of $\widehat{s}^{sym}(x)$; (II) the Taylor approximation in (2);
(III) the increase in variance (4) due to $\widehat{s}^{sym}$ not being the
exact score; and (IV) error from approximating
$\operatorname*{\mathbb{E}}_{x\sim f_{r}}[\widehat{s}^{sym^{\prime}}(x)]$ by
$\widehat{\mathcal{I}}_{r}$ in (3).

Unlike in the known-distribution case, clipping is necessary for bounding
error (I). The true score concentrates in expectation because $s_{r}(x)$ is
subgamma over $x\sim f_{r}$. However, $\widehat{s}_{r}(x)$ may not be so
concentrated. Consider the example
$f(x)=(1-\frac{2}{n})N(0,1)+\frac{1}{n}\delta_{-\sqrt{n}}+\frac{1}{n}\delta_{\sqrt{n}}$.
In this example, $x\sim f$ is usually constant but has a $\Theta(\frac{1}{n})$
chance of being quite large; in this case, it is likely that the large points
will not appear for the KDE but will appear exactly once for the second stage.
The KDE then gives them large scores (about $\sqrt{n}/r$), leading to
excessive final error ($\Theta(\frac{1}{r\sqrt{n}})$ not
$\Theta(\frac{1}{\sqrt{n}})$). Once the scores are clipped, however, we can
bound the error (I) with high probability via Bernstein’s inequality. The
clipping threshold $T$ is large enough to have negligible effect on the
expectations (III-IV); since the true score is subgaussian, with high
probability it is not clipped. Specifically, in the Gaussian + Symmetric Dirac
Deltas example above , the “excess error” in the above constant probability
event is now $O(\sqrt{\log\eta n}/(rn))$. Recalling that $r\approx 1/n^{1/13}$
in Theorem 1.1, the excess error after clipping is $\ll O(1/\sqrt{n})$.

Error (II) is bounded when $\varepsilon$ is small in a similar manner to
previous work in the known distribution case. For errors (III) and (IV), we
just need to show that, with high probability, our KDE $\widehat{f}_{r}\approx
f_{r}$ and $\widehat{s}^{sym}_{r}\approx s_{r}$, in different metrics but all
in expectation over $\widehat{f}$.

#### Comparison to Stone (1975).

Our approach, of taking an initial estimate and KDE and refining it with one
Newton step, is similar to Stone (1975). The main difference is that our work
needs more careful bounds: Stone (1975) shows convergence in probability to
$N(0,\frac{1}{n\mathcal{I}})$, which requires fixing the distribution $f$ and
failure probability $\delta$ before sending $n\to\infty$. By separating the
distribution dependence into $\mathcal{I}_{r}$, we can express and prove
bounds for any $f,n,\delta$.

We end this section with a short proof relating (4) to the score and Fisher
information.

######  Proposition 3.1.

For every antisymmetric function $g$ that is continuously differentiable and
whose derivative $g^{\prime}$ is integrable under $f_{r}$, we have

$\frac{\operatorname*{\mathbb{E}}_{{f_{r}}}[g^{2}(y)]}{\operatorname*{\mathbb{E}}_{{f_{r}}}[g^{\prime}(y)]^{2}}\geq\frac{1}{\mathcal{I}_{r}}$

with equality achieved when $g(y)=s_{r}(y)=f^{\prime}_{r}(y)/f_{r}(y)$.

######  Proof 3.2.

First, observe that by integration by parts, we have

$\operatorname*{\mathbb{E}}_{f_{r}}[g^{\prime}(y)]=\int_{\mathbb{R}}f_{r}(y)g^{\prime}(y)\,dy=[f_{r}(y)g(y)]_{-\infty}^{\infty}-\int_{\mathbb{R}}f^{\prime}_{r}(y)g(y)\,dy=-\int_{\mathbb{R}}f^{\prime}_{r}(y)g(y)\,dy$

where the last equality is by the symmetry of $f$ and antisymmetry of $g$.
Furthermore,

$\int_{\mathbb{R}}f^{\prime}_{r}(y)g(y)\,dy=\int_{\mathbb{R}}\frac{f^{\prime}_{r}(y)}{f_{r}(y)}g(y)f_{r}(y)\,dy=\operatorname*{\mathbb{E}}_{f_{r}}[s_{r}(y)g(y)]$

which means

$\operatorname*{\mathbb{E}}_{f_{r}}[g^{\prime}(y)]^{2}=\operatorname*{\mathbb{E}}_{f_{r}}[s_{r}(y)g(y)]^{2}\leq\operatorname*{\mathbb{E}}_{f_{r}}[s_{r}(y)^{2}]\operatorname*{\mathbb{E}}_{f_{r}}[g(y)]^{2}=\mathcal{I}_{r}\operatorname*{\mathbb{E}}_{f_{r}}[g(y)]^{2}$

by Cauchy-Schwarz, with equality achieved when $g(y)=s_{r}(y)$.

##  4 Key Steps in Proof

Here, we highlight the key steps of our proof. For the full proofs, see the
Appendix.

#### Notation.

Let $f^{*}$ be an arbitrary symmetric distribution with mean $\mu$ and
variance $\sigma^{2}$, and let $f_{r}$ be the $r$-smoothed version of $f^{*}$.
Let $s_{r}$ be the score function of $f_{r}$, so that
$s_{r}(x)=\frac{f_{r}^{\prime}(x)}{f_{r}(x)}$. Let
$\mathcal{I}_{r}=\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[s_{r}(x)^{2}\right]=-\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[s_{r}^{\prime}(x)\right]$ be the Fisher information of $f_{r}$.

Let $w_{r}$ be the density function of $\mathcal{N}(0,r^{2})$. Then, the
Kernel Density Estimate (KDE) $\widehat{f}_{r}$ from $N$ samples $Y_{1},\dots
Y_{N}\sim f^{*}$ is given by

$\widehat{f}_{r}(x)=\frac{1}{N}\sum_{i=1}^{N}w_{r}(x-Y_{i})$ (5)

It has score function $\widehat{s}_{r}$ with
$\widehat{s}_{r}(x)=\frac{\widehat{f}_{r}^{\prime}(x)}{\widehat{f}_{r}(x)}$.
Let $\widehat{s}_{r}^{\text{clip}}$ be the clipped KDE score from $N$ samples
with associated failure probability $\delta$, given by

$\widehat{s}_{r}^{\text{clip}}(x)=\text{sign}(\widehat{s}_{r}(x))\cdot\min\left(|\widehat{s}_{r}(x)|,\frac{2}{r}\sqrt{\log\frac{N}{\log\frac{1}{\delta}}}\right)$
(6)

Define the symmetrized clipped KDE score $\widehat{s}_{r}^{\text{sym}}$ from
$N$ samples, symmetrized around $y$, as

$\widehat{s}_{r}^{\text{sym}}(x)=\begin{cases}\widehat{s}_{r}^{\text{clip}}(x)&x\geq
y\\\ -\widehat{s}_{r}^{\text{clip}}(2y-x)&x<y\end{cases}$ (7)

In what follows, we first analyze the clipped KDE score (Section 4.1), before
showing that symmetrizing it at a $\mu+\varepsilon$ for small $|\varepsilon|$
does not add too much error (Section 4.2). Using similar techniques, we prove
that $\mathcal{I}_{r}$ can be computed directly from the KDE (Section 4.3).
Section 4.4 then analyzes the Newton step of the estimation, and finally
Section 4.5 assembles all the guarantees into Lemma 4.12, from which our main
result Theorem 1.1 follows as a corollary.

###  4.1 Clipped KDE Score

We first show that the clipped KDE score $\widehat{s}_{r}^{\text{clip}}$
approximates the true score $s_{r}$ in an $\ell_{2}$ sense:

######  Lemma 4.1 (Clipped KDE score error).

Let $\widehat{s}_{r}^{\text{clip}}$ be the clipped Kernel Density estimate
from $N$ samples, defined in (9). Let $\gamma>C$ be a parameter, for large
enough constant $C\geq 1$. Then for any $r\leq\sigma$ and
$\frac{N}{\log\frac{1}{\delta}}\geq\left(\frac{\gamma^{5/12}\sigma}{r}\right)^{6+\beta}$
for $\beta>0$, with probability $1-\delta$, we have that,

$\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[(\widehat{s}_{r}^{\text{clip}}(x)-s_{r}(x))^{2}\right]\lesssim\frac{\mathcal{I}_{r}}{\gamma}$

This holds even for asymmetric $f^{*}$ and $f_{r}$.

######  Proof 4.2.

We refer to the radius $t\sigma_{r}$ region around the true mean of $f^{*}$ as
the “typical region”, and to the region with density at least
$\alpha=\frac{1}{t^{3}\sigma_{r}}$ as the “large density region”. We break up
the expectation above into $3$ parts: (I) the typical, large density region,
(II) the typical, small density region, and (III) the atypical region. We then
bound the expectation in each of these regions individually.

To bound the expectation in regions (II) and (III), observe that both regions
(II) and (III) have total probability at most $O\left(\frac{1}{t^{2}}\right)$.
For our clipping threshold, we show that the expectation of
$\widehat{s}_{r}^{\text{clip}}(x)^{2}$ and $s_{r}$ on a region with this
probability is bounded by $O\left(\frac{\mathcal{I}_{r}}{\gamma}\right)$.

For region (I), we employ a binning argument. We first show that if we fix $x$
with $f_{r}(x)\geq\alpha$, then, for small enough $\varepsilon$ and for all
$|\zeta|\leq|\varepsilon|$, with probability $1-\delta$,
$\widehat{s}_{r}(x+\zeta)$ approximates $s_{r}(x+\zeta)$ up to error depending
on $\varepsilon,\delta,\alpha$ and $N$. That is, our KDE score approximates
the true score well within bins of size $\varepsilon$ with probability
$1-\delta$. Then, by union bounding over
$O\left(\frac{t\sigma_{r}}{\varepsilon}\right)$ bins, for appropriately chosen
$\varepsilon$, we show that, with probability $1-\delta$ for all $x$ in region
(I),
$|\widehat{s}_{r}^{\text{clip}}(x)-s_{r}(x)|\lesssim\sqrt{\frac{\mathcal{I}_{r}}{\gamma}}$
so that the expectation of $(\widehat{s}_{r}^{\text{clip}}(x)-s_{r}(x))^{2}$
in region (I) is bounded by $O\left(\frac{\mathcal{I}_{r}}{\gamma}\right)$.

Putting our bounds together then gives the claim.

###  4.2 Symmetrization

This section shows that $\widehat{s}_{r}^{\text{sym}}$ symmetrized at
$\mu+\varepsilon$ for small $\varepsilon$ has mean
$\approx\varepsilon\mathcal{I}_{r}$ and variance $\approx\mathcal{I}_{r}$.

######  Lemma 4.3 (Symmetrized Clipped KDE score variance).

Let $\widehat{s}_{r}^{\text{sym}}$ be the symmetrized clipped Kernel Density
Estimate score from $N$ samples, symmetrized around $\mu+\varepsilon$ for
$|\varepsilon|\leq r/60$, as defined in (12). Let $\gamma>C$ be a parameter
for large enough constant $C$. Then for any $r\leq\sigma$ and
$\frac{N}{\log\frac{1}{\delta}}\geq\left(\frac{\gamma^{5/12}\sigma}{r}\right)^{6+\beta}$
for $\beta>0$, if $|\varepsilon|\leq
r^{2}\sqrt{\frac{\mathcal{I}_{r}}{\gamma}}$, with probability $1-\delta$,

$|\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[\widehat{s}_{r}^{\text{sym}}(x)^{2}\right]-\mathcal{I}_{r}|\lesssim\frac{\mathcal{I}_{r}}{\sqrt{\gamma}}$

######  Proof 4.4.

First, we show that

$\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[(\widehat{s}_{r}^{\text{sym}}(x)-s_{r}(x))^{2}\right]\lesssim\operatorname*{\mathbb{E}}_{x\sim
f_{r}}[(\widehat{s}_{r}^{\text{clip}}(x)-s_{r}(x))^{2}]$

so that by the previous Lemma 4.1, it’s bounded by
$O\left(\frac{\mathcal{I}_{r}}{\gamma}\right)$. Then, we can show the claim
using the triangle inequality in $\ell_{2}$.

The Taylor approximation (2) leads to:

######  Lemma 4.5 (Symmetrized Clipped KDE score mean).

Let $\widehat{s}_{r}^{\text{sym}}$ be the symmetrized clipped Kernel Density
Estimate score from $N$ samples, symmetrized around $\mu+\varepsilon$ for
$|\varepsilon|\leq r/60$, as defined in (12). Let $\gamma>C$ be a parameter
for large enough constant $C$. Then for any $r\leq\sigma$ and
$\frac{N}{\log\frac{1}{\delta}}\geq\left(\frac{\gamma^{5/12}\sigma}{r}\right)^{6+\beta}$
for $\beta>0$, if $|\varepsilon|\leq
r^{2}\sqrt{\frac{\mathcal{I}_{r}}{\gamma}}$, with probability $1-\delta$,

$\left|\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[\widehat{s}_{r}^{\text{sym}}(x)\right]-\varepsilon\mathcal{I}_{r}\right|\lesssim\frac{\varepsilon\mathcal{I}_{r}}{\sqrt{\gamma}}$

###  4.3 Estimating $\mathcal{I}_{r}$

To perform a step of Newton’s method, we need an estimate of the Fisher
information $\mathcal{I}_{r}$. We show that
$\widehat{\mathcal{I}}_{r}=\operatorname*{\mathbb{E}}_{x\sim\widehat{f}_{r}}\left[\widehat{s}_{r}^{\text{sym}}(x)^{2}\right]$
is a good estimate whenever $\widehat{s}_{r}^{\text{sym}}$ satisfies the
conditions above.

######  Lemma 4.6 (Smoothed Fisher information Estimation).

Let $\gamma\geq C$ for large constant $C\geq 1$ be a parameter. Suppose we
have a function $\tilde{s}_{r}$ that satisfies for $r\leq\sigma$

$\left|\operatorname*{\mathbb{E}}_{x\sim
f_{r}}[\tilde{s}_{r}(x)^{2}]-\mathcal{I}_{r}\right|\lesssim\frac{\mathcal{I}_{r}}{\sqrt{\gamma}}$

and that
$|\tilde{s}_{r}(x)|\leq\frac{2}{r}\sqrt{\log\frac{N}{\log\frac{1}{\delta}}}$
for all $x$. Let $\widehat{f}_{r}$ be the kernel density estimate for $f_{r}$
from $N$ samples, as defined in (8). Then, for
$\frac{N}{\log\frac{1}{\delta}}\geq\left(\gamma^{5/12}\frac{\sigma}{r}\right)^{6+\beta}$
for some small constant $\beta>0$, with probability $1-\delta$, we have

$\left|\operatorname*{\mathbb{E}}_{x\sim\widehat{f}_{r}}[\tilde{s}_{r}(x)^{2}]-\mathcal{I}_{r}\right|\lesssim\frac{\mathcal{I}_{r}}{\sqrt{\gamma}}$

######  Proof 4.7.

We have

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim\widehat{f}_{r}}\left[\tilde{s}_{r}(x)^{2}\right]=\operatorname*{\mathbb{E}}_{x\sim
f_{r}}[\tilde{s}_{r}(x)^{2}]+\int_{-\infty}^{\infty}\left(\widehat{f}_{r}(x)-f_{r}(x)\right)\tilde{s}_{r}(x)^{2}dx$

As in the proof of Lemma 4.1, we again break up the integral above into $3$
parts and bound each part separately by
$O\left(\frac{\mathcal{I}_{r}}{\sqrt{\gamma}}\right)$. Finally, we make use of
our assumption that $\operatorname*{\mathbb{E}}_{x\sim
f_{r}}[\tilde{s}_{r}(x)^{2}]\approx\mathcal{I}_{r}$ along with our bound on
the integral to show the claim.

To conclude, we have with high probability ($1-\frac{\delta}{\xi}$) that our
KDE satisfies the following:

######  Property 4.8 (KDE Estimation Properties)

Let $f_{r}$ be the $r$-smoothed version of symmetric distribution $f^{*}$ in
Algorithm 1, with Fisher information $\mathcal{I}_{r}$. For parameters
$\gamma>C$ for some sufficiently large constant $C$ and $\xi$,
$\widehat{s}_{r}^{\text{sym}}$ satisfies that for symmetrization point
$\mu_{1}=\mu+\varepsilon$,

$\displaystyle\left|\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[\widehat{s}_{r}^{\text{sym}}(x)\right]-\varepsilon\mathcal{I}_{r}\right|\lesssim\frac{\varepsilon\mathcal{I}_{r}}{\sqrt{\gamma}}\quad\text{and}\quad\left|\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[\widehat{s}_{r}^{\text{sym}}(x)^{2}\right]-\mathcal{I}_{r}\right|\lesssim\frac{\mathcal{I}_{r}}{\sqrt{\gamma}}$

and
$|\widehat{s}_{r}^{\text{sym}}(x)|\leq\frac{2}{r}\sqrt{\log\frac{n}{\xi\log\frac{\xi}{\delta}}}$
for all $x$. Furthermore, the Fisher information estimate
$\widehat{\mathcal{I}}_{r}$ satisfies

$\left|\widehat{\mathcal{I}}_{r}-\mathcal{I}_{r}\right|\lesssim\frac{\mathcal{I}_{r}}{\sqrt{\gamma}}$

###  4.4 Local Estimation

We then show that Property 4.8 implies that Algorithm 1, which does one
approximate Newton step, gets high accuracy.

Algorithm 1 Local Estimation

#### Input Parameters:

  * •

$n$ samples $x_{1},\dots,x_{n}\sim f^{*}$, the symmetrized and clipped KDE
score function $\widehat{s}_{r}^{\text{sym}}$, symmetrization point $\mu_{1}$,
Fisher information estimate $\widehat{\mathcal{I}}_{r}$

  1. 1.

For each sample $x_{i}$, compute a perturbed sample
$x^{\prime}_{i}=x_{i}+\mathcal{N}(0,r^{2})$ where all the Gaussian noise are
drawn independently across all the samples.

  2. 2.

Compute
$\widehat{\varepsilon}=\frac{1}{\widehat{\mathcal{I}}_{r}n}\sum_{i=1}^{n}\widehat{s}_{r}^{\text{sym}}(x_{i}^{\prime})$.
Return $\widehat{\mu}=\mu_{1}-\widehat{\varepsilon}$.

######  Lemma 4.9 (Local Estimation).

In Algorithm 1, let $f_{r}$ be the $r$-smoothed version of symmetric
distribution $f^{*}$, with score function $s_{r}$ and Fisher information
$\mathcal{I}_{r}$. Suppose for parameters $\gamma,\xi$, and symmetrized
clipped KDE score $\widehat{s}^{\text{sym}}$ symmetrized around $\mu_{1}$,
Property 4.8 is satisfied. Then, with probability $1-\delta$, the output
$\widehat{\mu}$ of Algorithm 1 satisfies

$\left|\widehat{\mu}-\mu\right|\leq\left(1+O\left(\frac{1}{\sqrt{\gamma}}\right)\right)\sqrt{\frac{2\log\frac{2}{\delta}}{n\mathcal{I}_{r}}}+O\left(\frac{\sqrt{\log\frac{n}{\xi\log\frac{\xi}{\delta}}}}{r\mathcal{I}_{r}}\cdot\frac{\log\frac{2}{\delta}}{n}\right)+O\left(\frac{\varepsilon}{\sqrt{\gamma}}\right)$

######  Proof 4.10.

We bound $\widehat{\mu}-\mu$ using (2) for
$g(x)=\widehat{s}_{r}^{\text{sym}}(x)$. We apply Bernstein’s inequality to
concentrate $\widehat{\operatorname*{\mathbb{E}}}_{x\sim
f_{r}}[\widehat{s}_{r}^{\text{sym}}(x)]$. The first term in our bound is the
variance term and the second is the exponential term. The final term in our
error bound comes from the difference between
$\operatorname*{\mathbb{E}}[\widehat{s}_{r}^{\text{sym}}(x)]$ and
$\varepsilon\mathcal{I}_{r}$ bounded by Property 4.8.

###  4.5 Global Estimation

In order to perform our final estimation, we compute an initial estimate
$\mu_{1}$ of $\mu$, and our KDE $\widehat{f}_{r}$ with associated symmetrized
clipped score $\widehat{s}_{r}^{\text{sym}}$ around $\mu_{1}$, along with our
Fisher information estimate $\widehat{\mathcal{I}}_{r}$. We combine these with
our Local Estimation algorithm to obtain our final estimate $\widehat{\mu}$.
Lemma 4.12 shows our formal guarantee on the performance of our final estimate
$\widehat{\mu}$. Then,

For our initial estimate $\mu_{1}$, we make use of the median of pairwise
means estimator for symmetric distributions, implied by Minton and Price
(2014).

######  Lemma 4.11 (Median of pairwise means estimator).

Let $X_{1},X_{2},\dotsc,X_{n}$ be drawn from a symmetric distribution with
mean $\mu$ and variance $\sigma^{2}$. For every constant $C_{1}>0$ there
exists a constant $C_{2}$ such that
$\widehat{\mu}:=\operatorname*{median}_{i\in[n/2]}\frac{X_{2i-1}+X_{2i}}{2}$
satisfies

$|\widehat{\mu}-\mu|\leq
C_{2}\sigma\cdot\sqrt{\frac{\log\frac{2}{\delta}}{n}}$

with probability $1-\delta$, for all $\delta$ with $\log\frac{1}{\delta}\leq
C_{1}n$.

Algorithm 2 Global Estimation

#### Input parameters:

  * •

Failure probability $\delta$, Samples $x_{1},\dots,x_{n}\sim f^{*}$, smoothing
parameter $r$, approximation parameter $\xi>0$.

  1. 1.

First, use the first $n/\xi$ samples to compute an initial estimate $\mu_{1}$
of the mean $\mu$ by using the Median-of-pairwise-means estimator in Lemma
4.11.

  2. 2.

Use the next $n/\xi$ samples to compute the kernel density estimate
$\widehat{f}_{r}$ of $f_{r}$ (as defined in (8)), along with the associated
symmeterized, clipped KDE score $\widehat{s}_{r}^{\text{sym}}$ (as defined in
(12)), clipped at $\frac{2}{r}\sqrt{\log\frac{n}{\xi\log\frac{\xi}{\delta}}}$
and symmetrized around the initial estimate $\mu_{1}$. Compute the Fisher
information estimate
$\widehat{\mathcal{I}}_{r}=\operatorname*{\mathbb{E}}_{x\sim\widehat{f}_{r}}\left[\widehat{s}_{r}^{\text{sym}}(x)^{2}\right]$.

  3. 3.

Run Algorithm 1 using the remaining $n-\frac{2n}{\xi}$ samples, and return the
final estimate $\widehat{\mu}$.

######  Lemma 4.12 (Global Estimation).

Let $\xi>C$ for large enough constant $C>3$ be a parameter, and suppose
$\xi\leq\gamma\leq\left(\frac{n}{\xi\log\frac{1}{\delta}}\right)^{2/5-\alpha}$
for constant $\alpha>0$. For any $r\leq\sigma$ and
$\frac{n}{\log\frac{1}{\delta}}\geq\xi\left(\frac{\gamma^{5/12}\sigma}{r}\right)^{6+\alpha}$,
with probability $1-\delta$, Algorithm 2 outputs an estimate $\widehat{\mu}$
with

$|\widehat{\mu}-\mu|\leq\left(1+O\left(\frac{1}{\sqrt{\gamma}}\right)+O\left(\frac{1}{\xi}\right)\right)\sqrt{\frac{2\log\frac{2}{\delta}}{n\mathcal{I}_{r}}}+O\left(\frac{\sigma}{r\sqrt{\gamma}}\sqrt{\frac{\xi\log\frac{\xi}{\delta}}{n\mathcal{I}_{r}}}\right)$

######  Proof 4.13.

Combining Lemmas 4.11, 4.5, 4.3, 4.6, we know that
$\widehat{s}_{r}^{\text{sym}}(x)$ and $\widehat{\mathcal{I}}_{r}$ computed in
Steps 1 and 2 satisfy Property 4.8 with high probability. Invoking Lemma 4.9
on Step 3 yields the result.

Theorem 1.1 follows by setting $\gamma=\frac{1}{\eta^{2}}$,
$\xi=\frac{1}{\eta}$, and calculation.

Shivam Gupta and Eric Price are supported by NSF awards CCF-2008868,
CCF-1751040 (CAREER), and the NSF AI Institute for Foundations of Machine
Learning (IFML). Some of this work was done while Shivam Gupta was visiting UC
Berkeley. Jasper C.H. Lee is supported in part by the generous funding of a
Croucher Fellowship for Postdoctoral Research, NSF award DMS-2023239, NSF
Medium Award CCF-2107079 and NSF AiTF Award CCF-2006206.

## References

  * Acharya et al. (2011) Jayadev Acharya, Hirakendu Das, Ashkan Jafarpour, Alon Orlitsky, and Shengjun Pan.  Competitive closeness testing.  In _Proceedings of the 24th Annual Conference on Learning Theory_ , pages 47–68, 2011.
  * Acharya et al. (2017) Jayadev Acharya, Hirakendu Das, Alon Orlitsky, and Ananda Theertha Suresh.  A unified maximum likelihood approach for estimating symmetric properties of discrete distributions.  In _International Conference on Machine Learning_ , pages 11–21. PMLR, 2017.
  * Alon et al. (1999) Noga Alon, Yossi Matias, and Mario Szegedy.  The space complexity of approximating the frequency moments.  _J. Comput. Syst. Sci_ , 58(1):137–147, 1999\.
  * Anari et al. (2020) Nima Anari, Moses Charikar, Kirankumar Shiragur, and Aaron Sidford.  Instance based approximations to profile maximum likelihood.  _Advances in neural information processing systems_ , 33:20272–20285, 2020.
  * Asi and Duchi (2020a) Hilal Asi and John C Duchi.  Near instance-optimality in differential privacy.  _arXiv preprint arXiv:2005.10630_ , 2020a.
  * Asi and Duchi (2020b) Hilal Asi and John C Duchi.  Instance-optimality in differential privacy via approximate inverse sensitivity mechanisms.  _Advances in neural information processing systems_ , 33:14106–14117, 2020b.
  * Awasthi et al. (2022) Pranjal Awasthi, Abhimanyu Das, Weihao Kong, and Rajat Sen.  Trimmed maximum likelihood estimation for robust generalized linear model.  In _Proc. NeurIPS’22_ , 2022.
  * Bickel (1982) P. J. Bickel.  On Adaptive Estimation.  _The Annals of Statistics_ , 10(3):647 – 671, 1982.  10.1214/aos/1176345863.  URL https://doi.org/10.1214/aos/1176345863.
  * Catoni (2012) Olivier Catoni.  Challenging the empirical mean and empirical variance: A deviation study.  _Annales de l’Institut Henri Poincaré, Probabilités et Statistiques_ , 48(4):1148 – 1185, 2012.  10.1214/11-AIHP454.  URL https://doi.org/10.1214/11-AIHP454.
  * Charikar et al. (2019) Moses Charikar, Kirankumar Shiragur, and Aaron Sidford.  Efficient profile maximum likelihood for universal symmetric property estimation.  In _Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing_ , pages 780–791, 2019.
  * Cherapanamjeri et al. (2019) Yeshwanth Cherapanamjeri, Nicolas Flammarion, and Peter L. Bartlett.  Fast mean estimation with sub-gaussian rates.  In Alina Beygelzimer and Daniel Hsu, editors, _Proceedings of the Thirty-Second Conference on Learning Theory_ , volume 99 of _Proceedings of Machine Learning Research_ , pages 786–806. PMLR, 25–28 Jun 2019.
  * Cramér et al. (1946) H Cramér et al.  Mathematical methods of statistics.  _Mathematical methods of statistics._ , 1946.
  * Dang et al. (2023) Trung Dang, Jasper C.H. Lee, Maoyuan Song, and Paul Valiant.  Neighborhood optimality in mean estimation: Beyond worst-case, beyond sub-gaussian and beyond $1+\alpha$ moments.  2023\.
  * Daskalakis et al. (2018) Constantinos Daskalakis, Themis Gouleakis, Chistos Tzamos, and Manolis Zampetakis.  Efficient statistics, in high dimensions, from truncated samples.  In _2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)_ , pages 639–649. IEEE, 2018.
  * Devroye et al. (2016) Luc Devroye, Matthieu Lerasle, Gabor Lugosi, and Roberto I. Oliveira.  Sub-Gaussian mean estimators.  _Ann. Stat_ , 44(6):2695–2725, 2016.
  * Gupta et al. (2022) Shivam Gupta, Jasper C.H. Lee, Eric Price, and Paul Valiant.  Finite-sample maximum likelihood estimation of location.  In _NeurIPS_ , 2022.  URL https://arxiv.org/abs/2206.02348.
  * Gupta et al. (2023) Shivam Gupta, Jasper C.H. Lee, and Eric Price.  High-dimensional location estimation via norm concentration for subgamma vectors, 2023.  URL https://arxiv.org/abs/2302.02497.
  * Hao and Orlitsky (2019) Yi Hao and Alon Orlitsky.  The broad optimality of profile maximum likelihood.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Hopkins (2020) Samuel B. Hopkins.  Mean estimation with sub-Gaussian rates in polynomial time.  _The Annals of Statistics_ , 48(2):1193 – 1213, 2020.  10.1214/19-AOS1843.  URL https://doi.org/10.1214/19-AOS1843.
  * Huang et al. (2021) Ziyue Huang, Yuting Liang, and Ke Yi.  Instance-optimal mean estimation under differential privacy.  _Advances in Neural Information Processing Systems_ , 34:25993–26004, 2021.
  * Jerrum et al. (1986) Mark R. Jerrum, Leslie G. Valiant, and Vijay V. Vazirani.  Random generation of combinatorial structures from a uniform distribution.  _Theor. Comput. Sci_ , 43:169–188, 1986.
  * Lee and Valiant (2022a) Jasper C.H. Lee and Paul Valiant.  Optimal sub-gaussian mean estimation in very high dimensions.  In _Proc. ITCS 2022_ , 2022a.
  * Lee and Valiant (2022b) Jasper C.H. Lee and Paul Valiant.  Optimal sub-gaussian mean estimation in $\mathbb{R}$.  In _Proc. FOCS’21_ , pages 672–683, 2022b.
  * Lugosi and Mendelson (2019) Gábor Lugosi and Shahar Mendelson.  Sub-Gaussian estimators of the mean of a random vector.  _Ann. Stat._ , 47(2):783–794, 2019.
  * Minton and Price (2014) Gregory T Minton and Eric Price.  Improved concentration bounds for count-sketch.  In _Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms_ , pages 669–686. SIAM, 2014.
  * Nemirovsky and Yudin (1983) A.S. Nemirovsky and D.B. Yudin.  _Problem Complexity and Method Efficiency in Optimization_.  Wiley, 1983.
  * Pavlichin et al. (2019) Dmitri S Pavlichin, Jiantao Jiao, and Tsachy Weissman.  Approximate profile maximum likelihood.  _J. Mach. Learn. Res._ , 20(122):1–55, 2019.
  * Pettie and Wang (2021) Seth Pettie and Dingyu Wang.  Information theoretic limits of cardinality estimation: Fisher meets shannon.  In _Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing_ , pages 556–569, 2021.
  * Rao (1945) CR Rao.  Information and the accuracy attainable in the estimation of statistical parameters.  _Bull. Calcutta Math. Soc._ , 37:81–91, 1945.
  * Stone (1975) Charles J Stone.  Adaptive maximum likelihood estimators of a location parameter.  _The Annals of Statistics_ , 3(2):267–284, 1975\.
  * Valiant and Valiant (2016) Gregory Valiant and Paul Valiant.  Instance optimal learning of discrete distributions.  In _Proceedings of the forty-eighth annual ACM symposium on Theory of Computing_ , pages 142–155, 2016.
  * Valiant and Valiant (2017) Gregory Valiant and Paul Valiant.  An automatic inequality prover and instance optimal identity testing.  _SIAM Journal on Computing_ , 46(1):429–455, 2017\.
  * van der Vaart (2000) A.W. van der Vaart.  _Asymptotic Statistics_.  Cambridge University Press, 2000.  ISBN 9780521784504.
  * Vinayak et al. (2019) Ramya Korlakai Vinayak, Weihao Kong, Gregory Valiant, and Sham Kakade.  Maximum likelihood estimation for learning populations of parameters.  In _International Conference on Machine Learning_ , pages 6448–6457. PMLR, 2019.

##  Appendix A Definitions

Let $f^{*}$ be an arbitrary symmetric distribution with mean $\mu$ and
variance $\sigma^{2}$, and let $f_{r}$ be the $r$-smoothed version of $f^{*}$
with variance $\sigma_{r}^{2}=\sigma^{2}+r^{2}$. Let $s_{r}$ be the score
function of $f_{r}$, so that $s_{r}(x)=\frac{f_{r}^{\prime}(x)}{f_{r}(x)}$.
Let $\mathcal{I}_{r}=\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[s_{r}(x)^{2}\right]=-\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[s_{r}^{\prime}(x)\right]$ be the Fisher information of $f_{r}$.

Let $w_{r}$ be the density function of $\mathcal{N}(0,r^{2})$. We recall the
definition of the Kernel Density Estimate (KDE) $\widehat{f}_{r}$ from $N$
samples $Y_{1},\dots Y_{N}\sim f^{*}$, from (5).

$\widehat{f}_{r}(x)=\frac{1}{N}\sum_{i=1}^{N}w_{r}(x-Y_{i})$ (8)

It has score function $\widehat{s}_{r}$ with
$\widehat{s}_{r}(x)=\frac{\widehat{f}_{r}^{\prime}(x)}{\widehat{f}_{r}(x)}$.
We recall the definition of $\widehat{s}_{r}^{\text{clip}}$, the clipped KDE
score from $N$ samples with associated failure probability $\delta$, from (6).

$\widehat{s}_{r}^{\text{clip}}(x)=\text{sign}(\widehat{s}_{r}(x))\cdot\min\left(|\widehat{s}_{r}(x)|,\frac{2}{r}\sqrt{\log\frac{N}{\log\frac{1}{\delta}}}\right)$
(9)

We also recall the definition of $\widehat{s}_{r}^{\text{sym}}$, the
symmetrized clipped KDE score from $N$ samples, symmetrized around $y$, from
(7).

$\widehat{s}_{r}^{\text{sym}}(x)=\begin{cases}\widehat{s}_{r}^{\text{clip}}(x)&x\geq
y\\\ -\widehat{s}_{r}^{\text{clip}}(2y-x)&x<y\end{cases}$ (10)

##  Appendix B Clipped Kernel Density Estimate

In this section, we will analyze the _clipped Kernel Density Estimate_ score
function $\widehat{s}_{r}^{\text{clip}}$ of a distribution. Our main result in
this section is Lemma 4.1, which says that $\widehat{s}_{r}^{\text{clip}}$ is
a good approximation to the true score function $s_{r}$ of the $r$-smoothed
distribution in a specific sense.

###  B.1 Pointwise guarantees

In this section, we show that for any individual point $x$, the KDE score
$\widehat{s}_{r}(x)$ approximates $s_{r}(x)$ well, where $s_{r}$ is the true
score function of our $r$-smoothed distribution $f_{r}$. We begin by showing
that the KDE $\widehat{f}_{r}$ approximates the true density $f_{r}$
pointwise.

######  Lemma B.1 (Pointwise density estimate guarantee).

Let $\widehat{f}_{r}$ be the kernel density estimate of $f_{r}$ from $N$
samples $Y_{1},\dots,Y_{N}\sim f^{*}$, given by

$\widehat{f}_{r}(x)=\frac{1}{N}\sum_{i=1}^{N}w_{r}(x-Y_{i})$

where $w_{r}$ is the pdf of $\mathcal{N}(0,r^{2})$. For any fixed $x$, when
$N\geq\frac{3\log\frac{2}{\delta}}{f_{r}(x)r}$ we have that with probability
$1-\delta$

$\left|\widehat{f}_{r}(x)-f_{r}(x)\right|\leq\sqrt{\frac{3f_{r}(x)\log\frac{2}{\delta}}{Nr}}$

This holds even for asymmetric $f^{*},f_{r}$.

######  Proof B.2.

For every $x$, we have

$|w_{r}(x)|\leq\frac{1}{r}$

So, by multiplicative Chernoff, we have for $0\leq\varepsilon\leq 1$

$\Pr_{Y_{i}\sim
f^{*}}\left[\left|\frac{1}{N}\sum_{i=1}^{N}w_{r}(x-Y_{i})-\operatorname*{\mathbb{E}}_{Y\sim
f^{*}}[w_{r}(x-Y)]\right|\geq\varepsilon\operatorname*{\mathbb{E}}_{Y\sim
f^{*}}[w_{r}(x-Y)]\right]\leq
2\exp\left(-\frac{\varepsilon^{2}rNf_{r}(x)}{3}\right)$

The claim follows.

The next Lemma shows that the derivative of the KDE $\widehat{f}_{r}^{\prime}$
approximates the true derivative of the density function $f_{r}^{\prime}$
pointwise.

######  Lemma B.3 (Pointwise density derivative estimate guarantee).

Let $\widehat{f}_{r}$ be the kernel density estimate of $f_{r}$ from $N$
samples $Y_{1},\dots,Y_{N}\sim f^{*}$. For a fixed $x$, letting
$N\geq\frac{\log\frac{1}{\delta}}{rf_{r}(x)}$, we have that with probability
$1-\delta$,

$\left|\widehat{f}_{r}^{\prime}(x)-f_{r}^{\prime}(x)\right|\lesssim\sqrt{\frac{f_{r}(x)\log\frac{1}{\delta}}{Nr^{3}}}$

This holds even for asymmetric $f^{*},f_{r}$.

######  Proof B.4.

$\displaystyle\operatorname*{\mathbb{E}}_{Y\sim
f^{*}}[w_{r}^{\prime}(x-Y_{i})^{2}]=\operatorname*{\mathbb{E}}_{Y\sim
f^{*}}\left[\left(-w_{r}(x-Y)\frac{(x-Y)}{r^{2}}\right)^{2}\right]$
$\displaystyle=\frac{1}{r^{4}}\operatorname*{\mathbb{E}}_{Y\sim
f^{*}}\left[w_{r}(x-Y)^{2}(x-Y)^{2}\right]$
$\displaystyle\lesssim\frac{1}{r^{3}}\operatorname*{\mathbb{E}}_{Y\sim
f^{*}}[w_{r}(x-Y)]\quad\text{since }w_{r}(x-Y)(x-Y)^{2}\leq\frac{r}{\sqrt{2\pi
e}}$ $\displaystyle=\frac{f_{r}(x)}{r^{3}}$

Also,
$w_{r}^{\prime}(x-Y_{i})=-\frac{(x-Y_{i})}{\sqrt{2\pi}r^{3}}e^{-\frac{(x-Y_{i})^{2}}{2r^{2}}}$
is bounded in $[-1/r^{2},1/r^{2}]$. So, by Bernstein’s inequality,

$\displaystyle\Pr_{Y_{i}\sim
f^{*}}\left[\left|\frac{1}{N}\sum_{i=1}^{N}w_{r}^{\prime}(x-Y_{i})-\operatorname*{\mathbb{E}}_{Y\sim
f^{*}}[w_{r}^{\prime}(x-Y)]\right|\geq\varepsilon\right]$ $\displaystyle\leq
2\exp\left(-\Omega\left(\frac{\varepsilon^{2}}{\frac{f_{r}(x)}{Nr^{3}}+\frac{\varepsilon}{Nr^{2}}}\right)\right)$

So,

$\displaystyle|\widehat{f}_{r}^{\prime}(x)-f_{r}^{\prime}(x)|\lesssim\sqrt{\frac{f_{r}(x)\log\frac{1}{\delta}}{Nr^{3}}}+\frac{\log\frac{1}{\delta}}{Nr^{2}}$

Since $N\geq\frac{\log\frac{1}{\delta}}{f_{r}(x)r}$, the claim follows.

Finally, we have the main result of this section, which shows that the KDE
score $\widehat{s}_{r}$ approximates the true score $s_{r}$ pointwise.

######  Lemma B.5 (Pointwise Score Estimate Guarantee).

Let $\widehat{f}_{r}$ be the kernel density estimate of $f_{r}$ from $N$
samples $Y_{1},\dots,Y_{N}\sim f^{*}$. For fixed $x$,
$N\geq\frac{6\log\frac{4}{\delta}}{rf_{r}(x)}$, and the KDE score
$\widehat{s}_{r}$ defined in (8), given by

$\widehat{s}_{r}(x)=\frac{\widehat{f}_{r}^{\prime}(x)}{\widehat{f}_{r}(x)}$

we have that with probability $1-\delta$,

$\left|\widehat{s}_{r}(x)-s_{r}(x)\right|\lesssim\sqrt{\frac{\log\frac{1}{\delta}\log\frac{1}{rf_{r}(x)}}{Nr^{3}f_{r}(x)}}$

This holds even for asymmetric $f^{*},f_{r}$.

######  Proof B.6.

We have, by Lemmas B.1 and B.3, by a union bound, with probability $1-\delta$,

$\frac{\widehat{f}_{r}^{\prime}(x)}{\widehat{f}_{r}(x)}\leq\frac{f_{r}^{\prime}(x)+O\left(\sqrt{\frac{f_{r}(x)\log\frac{1}{\delta}}{Nr^{3}}}\right)}{f_{r}(x)\left(1-\sqrt{\frac{3\log\frac{4}{\delta}}{f_{r}(x)rN}}\right)}$

Since $N\geq\frac{6\log\frac{4}{\delta}}{rf_{r}(x)}$ we have that
$\sqrt{\frac{3\log\frac{4}{\delta}}{f_{r}(x)rN}}\leq 1/\sqrt{2}$. So,

$\displaystyle\widehat{s}_{r}(x)-s_{r}(x)$
$\displaystyle\lesssim\sqrt{\frac{\log\frac{1}{\delta}}{f_{r}(x)Nr^{3}}}+s_{r}(x)\sqrt{\frac{\log\frac{1}{\delta}}{f(x)rN}}$
$\displaystyle\lesssim\sqrt{\frac{\log\frac{1}{\delta}\log\frac{1}{rf_{r}(x)}}{Nr^{3}f_{r}(x)}}\quad\text{by
Lemma\leavevmode\nobreak\ \ref{lem:generic_density_large_score_small}}$

Similarly,

$\displaystyle\widehat{s}_{r}(x)-s_{r}(x)\gtrsim\sqrt{\frac{\log\frac{1}{\delta}\log\frac{1}{rf_{r}(x)}}{Nr^{3}f_{r}(x)}}$

###  B.2 Close-by scores are close

In this section, we show that for small enough $\varepsilon$,
$s_{r}(x+\varepsilon)$ and $s_{r}(x)$ are close to each other for the score
function $s_{r}$. We begin with the following utility lemma.

######  Lemma B.7.

Let $(X,Y,Z_{r})$ be the joint distribution such that $Y\sim f^{*}$,
$Z_{r}\sim\mathcal{N}(0,r^{2})$ are independent, and $X=Y+Z_{r}\sim f_{r}$.
For any $x$, and $t>0$, we have

$\Pr_{Z_{r}}[|Z_{r}|>rt|X=x]\leq\frac{e^{-t^{2}/2}}{\sqrt{2\pi}rf_{r}(x)}$

This holds even for asymmetric $f^{*},f_{r}$.

######  Proof B.8.

Recall that

$f_{r}(x)=\operatorname*{\mathbb{E}}_{Y\sim f^{*}}\left[w_{r}(x-Y)\right]$

where $w_{r}$ is the pdf of $\mathcal{N}(0,r^{2})$. So, we have

$\Pr_{X,Z_{r}}(\\{X=x\\}\cap\\{|Z_{r}|>rt\\})=\operatorname*{\mathbb{E}}_{Y\sim
f^{*}}\left[w_{r}(x-Y)1_{|x-Y|>rt}\right]\leq\frac{1}{\sqrt{2\pi}r}e^{-t^{2}/2}$

Since $w_{r}(x-Y)=\frac{1}{\sqrt{2\pi}r}e^{-\frac{(x-Y)^{2}}{2r^{2}}}$. Thus

$\Pr_{Z_{r}}[|Z_{r}|>rt|X=x]=\frac{\Pr_{X,Z_{r}}\left[\\{X=x\\}\cap\\{|Z_{r}|>rt\\}\right]}{\Pr_{X\sim
f_{r}}(X=x)}\leq\frac{e^{-t^{2}/2}}{f_{r}(x)\sqrt{2\pi}r}.$

The next lemma shows that $f_{r}(x+\varepsilon)$ is close to $f_{r}(x)$ for
small $\varepsilon$.

######  Lemma B.9.

Let $\varepsilon,x$ be such that
$\frac{8|\varepsilon|}{r}\sqrt{\log\frac{1}{rf_{r}(x)}}\leq 1$. We have,

$\frac{f_{r}(x+\varepsilon)}{f_{r}(x)}\leq
1+\frac{10|\varepsilon|}{r}\sqrt{\log\frac{1}{f_{r}(x)r}}$

This holds even for asymmetric $f^{*},f_{r}$.

######  Proof B.10.

Let $(X,Y,Z_{r})$ be the joint distribution such that $Y\sim f^{*}$,
$Z_{r}\sim\mathcal{N}(0,r^{2})$ are independent, and $X=Y+Z_{r}\sim f_{r}$.
For every $x$, by Lemma G.7, we have

$\frac{f_{r}(x+\varepsilon)}{f_{r}(x)}=\operatorname*{\mathbb{E}}_{Z_{r}\mid
x}\left[e^{\frac{2\varepsilon
Z_{r}-\varepsilon^{2}}{2r^{2}}}\right]\leq\operatorname*{\mathbb{E}}_{Z_{r}|x}\left[e^{\frac{\varepsilon
Z_{r}}{r^{2}}}\right]$

Without loss of generality, we assume that $\varepsilon>0$. Now, since
$\frac{8|\varepsilon|}{r}\sqrt{\log\frac{1}{rf_{r}(x)}}\leq 1$,

$\displaystyle\operatorname*{\mathbb{E}}_{Z_{r}\mid x}\left[e^{\varepsilon
Z_{r}/r^{2}}\right]$
$\displaystyle\leq\left(1+\frac{8\varepsilon}{r}\sqrt{\log\frac{1}{f_{r}(x)r}}\right)+\int_{1+\frac{8\varepsilon}{r}\sqrt{\log\frac{1}{f_{r}(x)r}}}^{\infty}\Pr_{Z_{r}|x}[e^{\varepsilon
z/r^{2}}\geq u]du$
$\displaystyle=1+\frac{8\varepsilon}{r}\sqrt{\log\frac{1}{f_{r}(x)r}}+\int_{1+\frac{8\varepsilon}{r}\sqrt{\log\frac{1}{f_{r}(x)r}}}^{\infty}\Pr_{Z_{r}|x}\left[Z_{r}\geq\frac{r^{2}\log
u}{\varepsilon}\right]du$
$\displaystyle=1+\frac{8\varepsilon}{r}\sqrt{\log\frac{1}{rf_{r}(x)}}+\int_{\log\left(1+\frac{8\varepsilon}{r}\sqrt{\log\frac{1}{rf_{r}(x)}}\right)}^{\infty}\Pr_{Z_{r}|x}\left[Z_{r}\geq
rv\right]\frac{\varepsilon}{r}e^{\varepsilon v/r}dv$
$\displaystyle\quad\left(\text{Substituting }v=\frac{r\log
u}{\varepsilon}\right)$ $\displaystyle\leq
1+\frac{8\varepsilon}{r}\sqrt{\log\frac{1}{f_{r}(x)r}}+\int_{4\sqrt{\log\frac{1}{f_{r}(x)r}}}^{\infty}\Pr_{Z_{r}|x}[Z_{r}\geq
rv]\frac{|\varepsilon|}{r}e^{\varepsilon v/r}dv$ $\displaystyle\leq
1+\frac{8\varepsilon}{r}\sqrt{\log\frac{1}{f_{r}(x)r}}+\frac{|\varepsilon|}{\sqrt{2\pi}}\int_{4\sqrt{\log\frac{1}{f_{r}(x)r}}}^{\infty}\frac{e^{-v^{2}/2+\varepsilon
v/r}}{r^{2}f_{r}(x)}dv\quad\text{by Lemma\leavevmode\nobreak\
\ref{lem:zcond}}$ $\displaystyle\leq
1+\frac{8\varepsilon}{r}\sqrt{\log\frac{1}{f_{r}(x)r}}+\frac{|\varepsilon|e^{\frac{2\varepsilon^{2}}{r^{2}}}}{r^{2}f_{r}(x)}\int_{4\sqrt{\log\frac{1}{f_{r}(x)r}}}^{\infty}\frac{e^{-\frac{\left(v-\frac{2\varepsilon}{r}\right)^{2}}{2}}}{\sqrt{2\pi}}dv$
$\displaystyle\leq
1+\frac{8\varepsilon}{r}\sqrt{\log\frac{1}{f_{r}(x)r}}+\frac{|\varepsilon|e^{\frac{2\varepsilon^{2}}{r^{2}}}}{r^{2}f_{r}(x)}\Pr_{W\sim\mathcal{N}(0,1)}\left[W\geq
4\sqrt{\log\frac{1}{f_{r}(x)r}}-\frac{2\varepsilon}{r}\right]$
$\displaystyle\leq
1+\frac{8\varepsilon}{r}\sqrt{\log\frac{1}{f_{r}(x)r}}+\frac{11|\varepsilon|}{10r^{2}f_{r}(x)}\Pr_{W\sim\mathcal{N}(0,1)}\left[W\geq\sqrt{2\log\frac{1}{rf_{r}(x)}}\right]$
since $f_{r}(x)\leq\frac{1}{\sqrt{2\pi}r}$, so that
$\frac{2|\varepsilon|}{r}\leq\frac{1}{4\sqrt{\log\frac{1}{rf_{r}(x)}}}\leq\frac{1}{4\log\sqrt{2\pi}}\sqrt{\log\frac{1}{rf_{r}(x)}}$
and since
$|\varepsilon|/r\leq\frac{1}{8\sqrt{\log\frac{1}{rf_{r}(x)}}}\leq\frac{1}{8\sqrt{\log\sqrt{2\pi}}}$
so that $e^{2\frac{\varepsilon^{2}}{r^{2}}}\leq 11/10$ $\displaystyle\leq
1+\frac{8\varepsilon}{r}\sqrt{\log\frac{1}{rf_{r}(x)}}+\frac{11|\varepsilon|}{10r}$
$\displaystyle\leq
1+\frac{10|\varepsilon|}{r}\sqrt{\log\frac{1}{rf_{r}(x)}}\quad\text{since
$\frac{11|\varepsilon|}{10}\leq\frac{2|\varepsilon|}{r}\sqrt{\log\sqrt{2\pi}}\leq\frac{2|\varepsilon|}{r}\sqrt{\log\frac{1}{rf_{r}(x)}}$}$

giving the result.

The next lemma shows that $f_{r}^{\prime}(x+\varepsilon)$ is close to
$f_{r}^{\prime}(x)$ for small $\varepsilon$.

######  Lemma B.11 (Close-by density derivatives are close).

Let $\varepsilon,x$ be such that
$\frac{20|\varepsilon|}{r}\sqrt{\log\frac{1}{f_{r}(x)r}}<1$. We have

$|f_{r}^{\prime}(x+\varepsilon)-f_{r}^{\prime}(x)|\lesssim\frac{|\varepsilon|}{r^{2}}f_{r}(x)\log\left(\frac{1}{rf_{r}(x)}\right)$

This holds even for asymmetric $f^{*},f_{r}$.

######  Proof B.12.

Let $w_{r}$ be the pdf of $\mathcal{N}(0,r^{2})$. We have that

$w_{r}^{\prime\prime}(x)=\frac{-r^{2}+x^{2}}{\sqrt{2\pi}r^{5}}e^{-\frac{x^{2}}{2r^{2}}}=\frac{-r^{2}+x^{2}}{r^{4}}w_{r}(x)=\frac{-1+2\log\left(\frac{1}{\sqrt{2\pi}r\cdot
w_{r}(x)}\right)}{r^{2}}w_{r}(x)$

since $x^{2}=2r^{2}\log\left(\frac{1}{\sqrt{2\pi}r\cdot w_{r}(x)}\right)$. So,
since $g(z)=z\log\left(\frac{1}{\sqrt{2\pi}r\cdot z}\right)$ is concave on
$[0,1]$, we have

$\displaystyle\operatorname*{\mathbb{E}}_{Y\sim
f^{*}}[w_{r}^{\prime\prime}(x-Y)]$
$\displaystyle=\frac{1}{r^{2}}\operatorname*{\mathbb{E}}_{Y\sim
f^{*}}\left[w_{r}(x-Y)\left(-1+2\log\left(\frac{1}{\sqrt{2\pi}r\cdot
w_{r}(x-Y)}\right)\right)\right]$
$\displaystyle\leq\frac{1}{r^{2}}\operatorname*{\mathbb{E}}_{Y\sim
f^{*}}[w_{r}(x-Y)]\left(-1+2\log\left(\frac{1}{\sqrt{2\pi}r\operatorname*{\mathbb{E}}_{Y\sim
f^{*}}[w_{r}(x-Y)]}\right)\right)\quad\text{by Jensen's inequality}$
$\displaystyle\lesssim\frac{f_{r}(x)\log\left(\frac{1}{f_{r}(x)\sqrt{2\pi}r}\right)}{r^{2}}$

So, by Taylor’s theorem, for some $|\zeta|<|\varepsilon|$

$\displaystyle w_{r}^{\prime}(x+\varepsilon-Y)=w_{r}^{\prime}(x-Y)+\varepsilon
w_{r}^{\prime\prime}(x+\zeta-Y)$

Now, by the above

$\displaystyle\operatorname*{\mathbb{E}}_{Y\sim
f^{*}}\left[w^{\prime\prime}_{r}(x+\zeta-Y)\right]$
$\displaystyle\lesssim\frac{f_{r}(x+\zeta)\log\left(\frac{1}{f_{r}(x+\zeta)\sqrt{2\pi}r}\right)}{r^{2}}$
$\displaystyle\lesssim\frac{f_{r}(x)\log\left(O\left(\frac{1}{f_{r}(x)r}\right)\right)}{r^{2}}\quad\text{Using
Lemma\leavevmode\nobreak\ \ref{lem:density_close}}$
$\displaystyle\lesssim\frac{f_{r}(x)\log\frac{1}{rf_{r}(x)}}{r^{2}}\quad\text{since
$rf_{r}(x)\leq\frac{1}{\sqrt{2\pi}}$}$

So, by the above,

$\displaystyle f_{r}^{\prime}(x+\varepsilon)-f_{r}^{\prime}(x)$
$\displaystyle\lesssim\varepsilon\operatorname*{\mathbb{E}}_{Y\sim
f^{*}}\left[w_{r}^{\prime\prime}(x+\zeta-Y)\right]$
$\displaystyle\lesssim\frac{\varepsilon}{r^{2}}f_{r}(x)\log\left(\frac{1}{rf_{r}(x)}\right)$

Similarly, by Taylor’s theorem, for some $|\zeta|<|\varepsilon|$,

$w_{r}^{\prime}(x-Y)=w_{r}^{\prime}(x+\varepsilon-Y)-\varepsilon
w_{r}^{\prime\prime}(x+\zeta-Y)$

so that

$\displaystyle
f_{r}^{\prime}(x)-f_{r}^{\prime}(x+\varepsilon)\lesssim-\frac{\varepsilon}{r^{2}}f_{r}(x)\log\left(\frac{1}{rf_{r}(x)}\right)$

The claim follows.

Finally, the main result of this section shows that $s_{r}(x+\varepsilon)$ is
close to $s_{r}(x)$ for small $\varepsilon$.

######  Lemma B.13 (Close-by scores are close).

Let $\varepsilon,x$ be such that
$\frac{20|\varepsilon|}{r}\sqrt{\log\frac{1}{rf_{r}(x)}}<1$. We have

$\left|s_{r}(x+\varepsilon)-s_{r}(x)\right|\lesssim\frac{|\varepsilon|}{r^{2}}\log\left(\frac{1}{rf_{r}(x)}\right)$

This holds even for asymmetric $f^{*},f_{r}$.

######  Proof B.14.

By Lemma B.9 and B.11, we have

$\frac{f^{\prime}_{r}(x+\varepsilon)}{f_{r}(x+\varepsilon)}\leq\frac{f_{r}^{\prime}(x)+O\left(\frac{|\varepsilon|}{r^{2}}f_{r}(x)\log\left(\frac{1}{rf_{r}(x)}\right)\right)}{f_{r}(x)\left(1-\frac{10|\varepsilon|}{r}\sqrt{\log\frac{1}{rf_{r}(x)}}\right)}$

Since $\frac{10|\varepsilon|}{r}\sqrt{\log\frac{1}{r\alpha}}<1/2$, we have

$\displaystyle\frac{f_{r}^{\prime}(x+\varepsilon)}{f_{r}(x+\varepsilon)}\leq\frac{f_{r}^{\prime}(x)}{f_{r}(x)}+O\left(\frac{|\varepsilon|}{r^{2}}\log\left(\frac{1}{rf_{r}(x)}\right)\right)+O\left(\frac{f_{r}^{\prime}(x)}{f_{r}(x)}\frac{|\varepsilon|}{r}\sqrt{\log\frac{1}{rf_{r}(x)}}\right)$

So,

$\displaystyle s_{r}(x+\varepsilon)-s_{r}(x)$
$\displaystyle\lesssim+\frac{|\varepsilon|}{r^{2}}\log\left(\frac{1}{rf_{r}(x)}\right)+s_{r}(x)\frac{|\varepsilon|}{r}\sqrt{\log\frac{1}{rf_{r}(x)}}$
$\displaystyle\lesssim\frac{|\varepsilon|}{r^{2}}\log\left(\frac{1}{rf_{r}(x)}\right)\quad\text{by
Lemma\leavevmode\nobreak\ \ref{lem:generic_density_large_score_small}}$

We can get the lower bound in the same way.

###  B.3 Bounding the clipped KDE error

In this section, we show that the clipped KDE score function
$\widehat{s}_{r}^{\text{clip}}$ approximates the true score function
$\widehat{s}_{r}^{\text{sym}}$ in a specific sense. We begin by showing that
sets that have small density under $f_{r}$ have small expected score.

######  Lemma B.15.

Let $S$ be any set with $\Pr_{f_{r}}[S]\leq\beta$. Let $|\varepsilon|\leq r/2$
and $|\varepsilon|\leq\frac{r}{\sqrt{\log\frac{1}{r^{2}\mathcal{I}_{r}}}}$.
Then, for the score function $s_{r}$ of $f_{r}$, we have

$\operatorname*{\mathbb{E}}_{x\sim f_{r}}[s_{r}(x+\varepsilon)^{2}1_{x\in
S}]\lesssim\frac{\beta}{r^{2}}\log\frac{1}{\beta}$

This holds even for asymmetric $f^{*},f_{r}$.

######  Proof B.16.

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim
f_{r}}[s_{r}^{2}(x+\varepsilon)\mathbbm{1}_{x\in S}]$
$\displaystyle=\int_{0}^{\infty}\Pr_{x\sim
f_{r}}[s_{r}^{2}(x+\varepsilon)\mathbbm{1}_{x\in S}\geq t]dt$
$\displaystyle\leq\int_{0}^{\infty}\min(\Pr_{x\sim f_{r}}[x\in S],\Pr_{x\sim
f_{r}}[s_{r}^{2}(x+\varepsilon)\geq t])dt$
$\displaystyle\leq\int_{0}^{\infty}\min(\beta,\Pr_{x\sim
f_{r}}[|s_{r}(x+\varepsilon)|\geq\sqrt{t}])dt$

So, by Lemma G.5, for some explicit constant $C>0$, we have:

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim
f_{r}}[s_{r}^{2}(x+\varepsilon)\mathbbm{1}_{x\in S}]$
$\displaystyle\lesssim\int_{0}^{\infty}\min(\beta,e^{-Ctr^{2}})dt$
$\displaystyle\lesssim\beta B+\int_{B}^{\infty}e^{-Ctr^{2}}dt$
$\displaystyle\lesssim\beta B+\frac{e^{-CBr^{2}}}{Cr^{2}}$

Thus, setting $B=\frac{\log\frac{1}{\beta}}{Cr^{2}}$ gives

$\displaystyle\operatorname*{\mathbb{E}}[s_{r}^{2}(x+\varepsilon)1_{x\in
S}]\lesssim\frac{\beta}{r^{2}}\log\frac{1}{\beta}$

The next lemma shows that for every small width region, the KDE score
$\widehat{s}$ approximates the true score well, as long as the density of that
region is large.

######  Lemma B.17 (Generic Error estimate within bin).

Let $f^{*}$ be an arbitrary distribution and let $f_{r}$ be the $r$-smoothed
version of $f^{*}$. Let $\widehat{f}_{r}$ be the kernel density estimate of
$f_{r}$ from $N$ samples $Y_{1},\dots,Y_{N}\sim f^{*}$. Let $x,\varepsilon,N$
be such that $N\geq\frac{6\log\frac{4}{\delta}}{rf_{r}(x)}$, and
$\frac{20|\varepsilon|}{r}\sqrt{\log\frac{1}{rf_{r}(x)}}<1$. Then, for the KDE
score $\widehat{s}_{r}$ defined in (8), with probability $1-\delta$, we have
that for all $|\zeta|\leq|\varepsilon|$ (simultaneously),

$|\widehat{s}_{r}(x+\zeta)-s_{r}(x+\zeta)|\lesssim\sqrt{\frac{\log\frac{1}{\delta}\log\frac{1}{rf_{r}(x)}}{Nr^{3}f_{r}(x)}}+\frac{|\varepsilon|}{r^{2}}\log\left(\frac{1}{rf_{r}(x)}\right)$

######  Proof B.18.

First, by Lemma B.5, we have that with probability $1-\delta$,

$|\widehat{s}_{r}(x)-s_{r}(x)|\lesssim\sqrt{\frac{\log\frac{1}{\delta}\log\frac{1}{rf_{r}(x)}}{Nr^{3}f_{r}(x)}}$

Now, by Lemma B.13, since $|\zeta|\leq|\varepsilon|$,

$|s_{r}(x+\zeta)-s_{r}(x)|\lesssim\frac{|\varepsilon|}{r^{2}}\log\left(\frac{1}{rf_{r}(x)}\right)$

and

$\displaystyle|\widehat{s}_{r}(x+\zeta)-\widehat{s}_{r}(x)|$
$\displaystyle\lesssim\frac{|\varepsilon|}{r^{2}}\log\left(\frac{1}{r\widehat{f}_{r}(x)}\right)$
$\displaystyle=\frac{|\varepsilon|}{r^{2}}\left(\log\left(\frac{1}{rf_{r}(x)}\right)+\log\left(\frac{f_{r}(x)}{\widehat{f}_{r}(x)}\right)\right)$
$\displaystyle\leq\frac{|\varepsilon|}{r^{2}}\left(\log\left(\frac{1}{rf_{r}(x)}\right)+\log\left(1+\frac{1}{\sqrt{2}}\right)\right)\quad\text{by
Lemma\leavevmode\nobreak\ \ref{lem:pointwise_density_estimate} and since
$N\geq\frac{6\log\frac{4}{\delta}}{rf_{r}(x)}$}$
$\displaystyle\lesssim\frac{|\varepsilon|}{r^{2}}\log\left(\frac{1}{rf_{r}(x)}\right)\quad\text{since
$rf_{r}(x)\leq\frac{1}{\sqrt{2\pi}}$, so $\log\frac{1}{rf_{r}(x)}=\Omega(1)$}$

Putting everything together, with probability $1-\delta$, for all
$|\zeta|\leq|\varepsilon|$,

$\displaystyle|\widehat{s}_{r}(x+\zeta)-s_{r}(x+\zeta)|$
$\displaystyle\leq|\widehat{s}_{r}(x+\zeta)-\widehat{s}_{r}(x)|+|\widehat{s}_{r}(x)-s_{r}(x)|+|s_{r}(x)-s_{r}(x+\zeta)|$
$\displaystyle\lesssim\sqrt{\frac{\log\frac{1}{\delta}\log\frac{1}{rf_{r}(x)}}{Nr^{3}f_{r}(x)}}+\frac{|\varepsilon|}{r^{2}}\log\left(\frac{1}{rf_{r}(x)}\right)$

The next lemma shows that for all points with density larger than $\alpha$
within a $t\sigma$ radius around the true mean, the KDE score approximates the
true score well.

######  Lemma B.19 (Generic Error estimate over large density region).

Let $f^{*}$ be an arbitrary distribution with mean $\mu$ and variance
$\sigma^{2}$, and let $f_{r}$ be the $r$-smoothed version of $f^{*}$, with
variance $\sigma_{r}^{2}=\sigma^{2}+r^{2}$. Let $\widehat{s}_{r}$ be the score
of the kernel density estimate of $f_{r}$ from $N$ samples
$Y_{1},\dots,Y_{N}\sim f^{*}$, as defined in (8). Let $\alpha>0$ and let
$N\geq\frac{6\log\left(\frac{4}{\delta}\left(\frac{2\sqrt{\alpha
N}t\sigma_{r}}{\sqrt{r}}+1\right)\right)+400\log\frac{1}{\alpha r}}{\alpha
r}$. Then with probability $1-\delta$, we have that,

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[(\widehat{s}_{r}(x)-s_{r}(x))^{2}\mathbbm{1}_{\\{|x-\mu|\leq
t\sigma_{r}\text{ and
}f_{r}(x)\geq\alpha\\}}\right]\lesssim\frac{\log\left(\frac{1}{\delta}\left(\frac{2t\sigma_{r}\sqrt{\alpha
N}}{\sqrt{r}}+1\right)\right)}{\alpha Nr^{3}}\log^{2}\frac{1}{\alpha r}$

######  Proof B.20.

Consider contiguous intervals of length $\varepsilon$ starting from
$\mu-t\sigma_{r}$ so that the last interval covers $\mu+t\sigma_{r}$, and let
$S$ be the set of the smallest $y$ such that $f(y)\geq\alpha$ in each of these
intervals, if one exists. Note that
$|S|\leq\frac{2t\sigma_{r}}{\varepsilon}+1$. Then, we have that

$\left\\{x:|x-\mu|\leq t\sigma_{r}\text{ and
}f_{r}(x)\geq\alpha\right\\}\subseteq\left\\{[y-\varepsilon,y+\varepsilon]|y\in
S\right\\}$

Now, for $\varepsilon=\sqrt{\frac{r}{\alpha N}}$ and $y\in S$, since
$N\geq\frac{6\log\left(\frac{4}{\delta}\left(\frac{2\sqrt{\alpha
N}t\sigma_{r}}{\sqrt{r}}+1\right)\right)}{\alpha
r}\geq\frac{6\log\frac{4|S|}{\delta}}{rf_{r}(y)}$ and
$\frac{20|\varepsilon|}{r}\sqrt{\log\frac{1}{rf_{r}(y)}}\leq\frac{20}{\sqrt{\alpha
rN}}\sqrt{\log\frac{1}{\alpha r}}\leq 1$, by Lemma B.17, we have that with
probability $1-\frac{\delta}{|S|}$, for all $|\zeta|\leq\varepsilon$
(simultaneously),

$\displaystyle|\widehat{s}_{r}(y+\zeta)-s_{r}(y+\zeta)|$
$\displaystyle\lesssim\sqrt{\frac{\log\frac{|S|}{\delta}\log\frac{1}{rf_{r}(y)}}{Nr^{3}f_{r}(y)}}+\sqrt{\frac{1}{\alpha
Nr^{3}}}\log\frac{1}{rf_{r}(y)}$
$\displaystyle\lesssim\sqrt{\frac{\log\left(\frac{1}{\delta}\left(\frac{2t\sigma_{r}\sqrt{\alpha
N}}{\sqrt{r}}+1\right)\right)}{\alpha Nr^{3}}}\log\frac{1}{\alpha r}$

So by a union bound, with probability $1-\delta$, for all $x$ such that
$|x-\mu|\leq t\sigma_{r}$ and $f(x)\geq\alpha$ simultaneously,

$|\widehat{s}_{r}(x)-s_{r}(x)|\lesssim\sqrt{\frac{\log\left(\frac{1}{\delta}\left(\frac{2t\sigma_{r}\sqrt{\alpha
N}}{\sqrt{r}}+1\right)\right)}{\alpha Nr^{3}}}\log\frac{1}{\alpha r}$

So,

$\operatorname*{\mathbb{E}}_{x\sim
f_{r}}[(\widehat{s}_{r}(x)-s_{r}(x))^{2}\mathbbm{1}_{|x-\mu|\leq
t\sigma_{r}\text{ and
}f_{r}(x)\geq\alpha}]\lesssim\frac{\log\left(\frac{1}{\delta}\left(\frac{2t\sigma_{r}\sqrt{\alpha
N}}{\sqrt{r}}+1\right)\right)}{\alpha Nr^{3}}\log^{2}\frac{1}{\alpha r}$

The next lemma instantiates the previous one with a particular value of $t$
and $\alpha$ based on our desired failure probability and the number of
samples.

######  Lemma B.21 (Error estimate over large density region (instantiated)).

Let $f^{*}$ be an arbitrary distribution with mean $\mu$ and variance
$\sigma^{2}$, and let $f_{r}$ be the $r$-smoothed version of $f^{*}$, with
variance $\sigma_{r}^{2}=\sigma^{2}+r^{2}$ and Fisher information
$\mathcal{I}_{r}$. Let $\widehat{s}_{r}$ be the score of the kernel density
estimate of $f_{r}$ from $N$ samples $Y_{1},\dots,Y_{N}\sim f^{*}$, as defined
in (9). Let $\gamma\geq C$ for large enough constant $C>1$ be a parameter. Let
$t=\sqrt{\frac{\gamma\log\frac{N}{\mathcal{I}_{r}r^{2}\log\frac{1}{\delta}}}{\mathcal{I}_{r}r^{2}}}$,
$\alpha=\frac{1}{t^{3}\sigma_{r}}$. Then for any $r\leq\sigma$ and
$\frac{N}{\log\frac{1}{\delta}}\geq\left(\gamma^{5/12}\frac{\sigma}{r}\right)^{6+\beta}$
for any constant $\beta>0$, with probability $1-\delta$, we have that,

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[(\widehat{s}_{r}(x)-s_{r}(x))^{2}\mathbbm{1}_{\\{|x-\mu|\leq
t\sigma_{r}\text{ and
}f_{r}(x)\geq\alpha\\}}\right]\lesssim\frac{\mathcal{I}_{r}}{\gamma}$

######  Proof B.22.

First, note that since $r\leq\sigma$,

$\displaystyle\sigma_{r}^{2}=\sigma^{2}+r^{2}\leq 2\sigma^{2}$

Also, our setting of $N$ implies that WLOG

$\frac{N}{\log\frac{1}{\delta}}\geq\left(\frac{\gamma^{5/12}\sigma\log\frac{N}{\log\frac{1}{\delta}}}{r}\right)^{6}$

since $N\geq C\log\frac{1}{\delta}$. So,

$\frac{\sigma}{r}\leq\left(\frac{N}{\log\frac{1}{\delta}}\right)^{1/6}\cdot\frac{1}{\gamma^{5/12}\log\frac{N}{\log\frac{1}{\delta}}}\leq\left(\frac{N}{\log\frac{1}{\delta}}\right)^{1/6}$
(11)

We will first check that this $N$ satisfies the condition required to invoke
Lemma B.19 that
$N\geq\frac{6\log\left(\frac{4}{\delta}\left(\frac{2\sqrt{\alpha
N}t\sigma_{r}}{\sqrt{r}}+1\right)\right)+400\log\frac{1}{\alpha r}}{\alpha
r}$. To do this, we will individually upper bound $\frac{1}{\alpha r}$ and
$\frac{2t\sigma_{r}\sqrt{\alpha N}}{\sqrt{r}}$.

We have,

$\displaystyle\frac{1}{\alpha r}$
$\displaystyle=\frac{\sigma_{r}}{r}\left(\frac{\gamma\log\frac{N}{\mathcal{I}_{r}r^{2}\log\frac{1}{\delta}}}{\mathcal{I}_{r}r^{2}}\right)^{3/2}\quad\text{since
$\alpha=\frac{1}{t^{3}\sigma_{r}}$ and
$t=\sqrt{\frac{\gamma\log\frac{N}{\mathcal{I}_{r}r^{2}\log\frac{1}{\delta}}}{\mathcal{I}_{r}r^{2}}}$}$
$\displaystyle\leq\left(\frac{\sigma_{r}}{r}\right)^{4}\gamma^{3/2}\log^{3/2}\frac{N\sigma_{r}^{2}}{r^{2}\log\frac{1}{\delta}}\quad\text{since
$\mathcal{I}_{r}\geq\frac{1}{\sigma_{r}^{2}}$}$
$\displaystyle\leq\left(\frac{2\sigma}{r}\right)^{4}\gamma^{3/2}\log^{3/2}\left(\frac{2N\sigma^{2}}{r^{2}\log\frac{1}{\delta}}\right)\quad\text{since
$\sigma_{r}^{2}\leq 2\sigma^{2}$}$ $\displaystyle\leq
16\frac{N^{4/6}}{\gamma^{5/3}\log^{4}(\frac{N}{\log\frac{1}{\delta}})\log^{4/6}\frac{1}{\delta}}\gamma^{3/2}\log^{3/2}\left(2\left(\frac{N}{\log\frac{1}{\delta}}\right)^{4/3}\right)\quad\text{by
\eqref{eq:sigma_over_r_bound}}$
$\displaystyle\leq\frac{N}{\gamma^{1/10}\log(\frac{1}{\delta})\log^{2}\left(\frac{N}{\log\frac{1}{\delta}}\right)}\quad\text{since
$\gamma\geq C$ for $C$ large enough constant, and
$\frac{\log\frac{1}{\delta}}{N}\leq 1$}$

To further justify the last line above, observe that
$\frac{\gamma^{3/2}}{\gamma^{5/3}}\leq\frac{1}{\gamma^{1/6}}=\frac{1}{\gamma^{1/10}\cdot\gamma^{1/15}}$,
and that for large enough constant $C$, since $\gamma>C$, $\gamma^{1/15}$ can
be made larger than any fixed constant. Also note that
$\log^{3/2}(2(\frac{N}{\log\frac{1}{\delta}})^{4/3})\leq\log^{2}\frac{N}{\log\frac{1}{\delta}}$
for large enough $C$ since $\frac{N}{\log\frac{1}{\delta}}\geq\gamma\geq C$.
So, the inequality follows.

Next, we bound $\frac{2t\sigma_{r}\sqrt{\alpha N}}{\sqrt{r}}$.

$\displaystyle\frac{2t\sigma_{r}\sqrt{\alpha N}}{\sqrt{r}}$
$\displaystyle=2\sqrt{\frac{N\sigma_{r}}{tr}}\quad\text{since
$\alpha=\frac{1}{t^{3}\sigma_{r}}$}$
$\displaystyle=2\sqrt{\frac{N\sigma_{r}}{\sqrt{\frac{\gamma\log\frac{N}{\mathcal{I}_{r}r^{2}\log\frac{1}{\delta}}}{\mathcal{I}_{r}r^{2}}}r}}\quad\text{since
$t=\sqrt{\frac{\gamma\log\frac{N}{\mathcal{I}_{r}r^{2}\log\frac{1}{\delta}}}{\mathcal{I}_{r}r^{2}}}$}$
$\displaystyle\leq
4\sqrt{\frac{N\sigma}{r\sqrt{\gamma\log\frac{N}{\log\frac{1}{\delta}}}}}\quad\text{since
$\mathcal{I}_{r}\leq\frac{1}{r^{2}}$ and $\sigma_{r}^{2}\leq 2\sigma^{2}$}$
$\displaystyle\leq
4\sqrt{\frac{N}{\sqrt{\gamma\log\frac{N}{\log\frac{1}{\delta}}}}\cdot\left(\frac{N}{\log\frac{1}{\delta}}\right)^{1/6}}\quad\text{by
\eqref{eq:sigma_over_r_bound}}$ $\displaystyle\leq
4N\cdot\left(\frac{N}{\log\frac{1}{\delta}}\right)^{1/12}\quad\text{since
$\gamma\geq 1$, $\frac{N}{\log\frac{1}{\delta}}\geq 1$}$

So, we can now check the condition required to invoke Lemma B.19. We have,

$\displaystyle\frac{6\log\left(\frac{4}{\delta}\left(\frac{2\sqrt{\alpha
N}t\sigma_{r}}{\sqrt{r}}+1\right)\right)+400\log\frac{1}{\alpha r}}{\alpha r}$
$\displaystyle\leq\left(6\log\left(\frac{4}{\delta}\left(4N\cdot\left(\frac{N}{\log\frac{1}{\delta}}\right)^{1/12}+1\right)\right)+400\log\frac{N}{\log\frac{1}{\delta}}\right)\left(\frac{N}{\gamma^{1/10}\log^{2}\left(\frac{N}{\log\frac{1}{\delta}}\right)\log\frac{1}{\delta}}\right)$
$\displaystyle\leq N\quad\text{since $\gamma\geq C$}$

So, by Lemma B.19, we have

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[(\widehat{s}_{r}(x)-s_{r}(x))^{2}\mathbbm{1}_{\\{|x-\mu|\leq
t\sigma_{r}\text{ and }f_{r}(x)\geq\alpha\\}}\right]$
$\displaystyle\lesssim\frac{\log\left(\frac{1}{\delta}\left(\frac{2\sigma_{r}\sqrt{\alpha
N}}{\sqrt{r}}+1\right)\right)}{\alpha Nr^{3}}\log^{2}\frac{1}{\alpha r}$

To bound the RHS above by $O\left(\mathcal{I}_{r}/\gamma\right)$ as required,
we will first bound $\frac{1}{\alpha Nr^{3}}$.

$\displaystyle\frac{1}{\alpha Nr^{3}}$
$\displaystyle=\frac{\sigma_{r}}{Nr^{3}}\left(\frac{\gamma\log\frac{N}{\mathcal{I}_{r}r^{2}\log\frac{1}{\delta}}}{\mathcal{I}_{r}r^{2}}\right)^{3/2}\quad\text{since
$\alpha=\frac{1}{t^{3}\sigma_{r}}$ and
$t=\sqrt{\frac{\gamma\log\frac{N}{\mathcal{I}_{r}r^{2}\log\frac{1}{\delta}}}{\mathcal{I}_{r}r^{2}}}$}$
$\displaystyle=\frac{\mathcal{I}_{r}}{\gamma}\left(\frac{\sigma_{r}}{Nr^{6}}\frac{\gamma^{5/2}}{\mathcal{I}_{r}^{5/2}}\log^{3/2}\frac{N}{\mathcal{I}_{r}r^{2}\log\frac{1}{\delta}}\right)$
$\displaystyle\leq\frac{\mathcal{I}_{r}}{\gamma}\left(\frac{\sigma_{r}^{6}\gamma^{5/2}\log^{3/2}\frac{N\sigma_{r}^{2}}{r^{2}\log\frac{1}{\delta}}}{Nr^{6}}\right)\quad\text{since
$\mathcal{I}_{r}\geq\frac{1}{\sigma_{r}^{2}}$}$
$\displaystyle\lesssim\frac{\mathcal{I}_{r}}{\gamma}\left(\frac{\sigma^{6}\gamma^{5/2}\log^{3/2}\frac{4N\sigma^{2}}{r^{2}\log\frac{1}{\delta}}}{Nr^{6}}\right)\quad\text{since
$\sigma_{r}^{2}\leq 2\sigma^{2}$}$
$\displaystyle\leq\frac{\mathcal{I}_{r}}{\gamma}\left(\frac{\log^{3/2}(4\left(\frac{N}{\log\frac{1}{\delta}}\right)^{4/3})}{\log^{6}\left(\frac{N}{\log\frac{1}{\delta}}\right)\log\frac{1}{\delta}}\right)\quad\text{by
\eqref{eq:sigma_over_r_bound}}$
$\displaystyle\lesssim\frac{\mathcal{I}_{r}}{\gamma\log^{4}\left(\frac{N}{\log\frac{1}{\delta}}\right)\log\frac{1}{\delta}}$

So, plugging in everything,

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[(\widehat{s}_{r}(x)-s_{r}(x))^{2}\mathbbm{1}_{\\{|x-\mu|\leq
t\sigma_{r}\text{ and }f_{r}(x)\geq\alpha\\}}\right]$
$\displaystyle\lesssim\frac{\log\left(\frac{1}{\delta}\left(\frac{2\sigma_{r}\sqrt{\alpha
N}}{\sqrt{r}}+1\right)\right)}{\alpha Nr^{3}}\log^{2}\frac{1}{\alpha r}$
$\displaystyle\lesssim\frac{\mathcal{I}_{r}}{\gamma\log^{4}\left(\frac{N}{\log\frac{1}{\delta}}\right)\log\frac{1}{\delta}}\log\left(\frac{4N\cdot\left(\frac{N}{\log\frac{1}{\delta}}\right)^{1/12}+1}{\delta}\right)\log^{2}\left(\left(\frac{N}{\log\frac{1}{\delta}}\right)^{4/6}\right)$
$\displaystyle\lesssim\frac{\mathcal{I}_{r}}{\gamma}$

The lemmas so far have shown that the KDE score $\widehat{s}_{r}$ approximates
the true score $s_{r}$ well in large denstiy regions in the typical $t\sigma$
radius around the true mean. The next lemma shows that the same guarantee
holds for the clipped KDE score $\widehat{s}_{r}^{\text{clip}}$.

######  Lemma B.23 (Error estimate over large density region for clipped KDE).

Let $f^{*}$ be an arbitrary distribution with mean $\mu$ and variance
$\sigma^{2}$, and let $f_{r}$ be the $r$-smoothed version of $f^{*}$, with
variance $\sigma_{r}^{2}=\sigma^{2}+r^{2}$. Let
$\widehat{s}_{r}^{\text{clip}}$ be the clipped kernel density estimate score
from $N$ samples, as defined in (8). Let $\gamma\geq C$ for large enough
constant $C>1$ be a parameter. Let
$t=\sqrt{\frac{\gamma\log\frac{N}{\mathcal{I}_{r}r^{2}\log\frac{1}{\delta}}}{\mathcal{I}_{r}r^{2}}}$,
$\alpha=\frac{1}{t^{3}\sigma_{r}}$.Then for any $r\leq\sigma$ and
$\frac{N}{\log\frac{1}{\delta}}\geq\left(\frac{\gamma^{5/12}\sigma}{r}\right)^{6+\beta}$
for $\beta>0$, with probability $1-\delta$, we have that,

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[(\widehat{s}_{r}^{\text{clip}}(x)-s_{r}(x))^{2}\mathbbm{1}_{\\{|x-\mu|\leq
t\sigma_{r}\text{ and
}f_{r}(x)\geq\alpha\\}}\right]\lesssim\frac{\mathcal{I}_{r}}{\gamma}$

######  Proof B.24.

Note that our condition that
$\frac{N}{\log\frac{1}{\delta}}\geq\left(\frac{\gamma^{5/12}\sigma}{r}\right)^{6+\beta}$
implies

$\frac{\sigma}{r}\leq\left(\frac{N}{\log\frac{1}{\delta}}\right)^{1/6}$

Also, since $r\leq\sigma$,
$\frac{N}{\log\frac{1}{\delta}}\geq(\gamma^{5/12})^{6+\beta}\geq\gamma^{5/2}$.

So, by Lemma G.1, for $x$ such that $f_{r}(x)\geq\alpha$,

$\displaystyle|s_{r}(x)|$
$\displaystyle\leq\frac{1}{r}\sqrt{2\log\frac{1}{\sqrt{2\pi}r\alpha}}$
$\displaystyle=\frac{1}{r}\sqrt{2\log\left(\frac{\sigma_{r}}{\sqrt{2\pi}r}\left(\frac{\gamma\log\frac{N}{\mathcal{I}_{r}r^{2}\log\frac{1}{\delta}}}{\mathcal{I}_{r}r^{2}}\right)^{3/2}\right)}\quad\text{since
$\alpha=\frac{1}{t^{3}\sigma_{r}}$ and
$t=\sqrt{\frac{\gamma\log\frac{N}{\mathcal{I}_{r}r^{2}\log\frac{1}{\delta}}}{\mathcal{I}_{r}r^{2}}}$}$
$\displaystyle\leq\frac{1}{r}\sqrt{2\log\left(\frac{\sigma_{r}^{4}}{\sqrt{2\pi}r^{4}}\left(\gamma\log\frac{\sigma_{r}^{2}N}{r^{2}\log\frac{1}{\delta}}\right)^{3/2}\right)}\quad\text{since
$\mathcal{I}_{r}\geq\frac{1}{\sigma_{r}^{2}}$}$
$\displaystyle\leq\frac{1}{r}\sqrt{2\log\left(\frac{16}{\sqrt{2\pi}}\left(\frac{N}{\log\frac{1}{\delta}}\right)^{4/6}\left(\gamma\log\left(4\left(\frac{N}{\log\frac{1}{\delta}}\right)^{4/3}\right)\right)^{3/2}\right)}$
since $\sigma_{r}^{2}\leq 2\sigma^{2}$ and using
$\sigma/r\leq\left(\frac{N}{\log\frac{1}{\delta}}\right)^{1/6}$
$\displaystyle\leq\frac{2}{r}\sqrt{\log\frac{N}{\log\frac{1}{\delta}}}\quad\text{since
$\frac{N}{\log\frac{1}{\delta}}\geq\gamma^{5/2}\geq C^{5/2}$ for a
sufficiently large constant $C$}$

Then, since $\widehat{s}_{r}^{\text{clip}}$ is clipped at
$\frac{2}{r}\sqrt{\log\frac{N}{\log\frac{1}{\delta}}}$ by definition in (9),
by Lemma B.21, we have the claim.

The next lemma shows that for small density sets, for any function that is
clipped appropriately, the error incurred relative to the true score function
is small.

######  Lemma B.25.

Let $f^{*}$ be an arbitrary distribution, and let $f_{r}$ be the $r$-smoothed
version of $f^{*}$. Let $s_{r}$ be the score function of $f_{r}$, and let
$\mathcal{I}_{r}$ be the Fisher information. Let $\gamma\geq C$ for large
enough constant $C$, $\frac{N}{\log\frac{1}{\delta}}\geq\gamma$, and let
$\tilde{s}$ be any function with
$|\tilde{s}_{r}(x)|\leq\frac{2}{r}\sqrt{\log\frac{N}{\log\frac{1}{\delta}}}$
for all $x$. Let $S$ be a set with $\Pr[S]\leq\frac{1}{t^{2}}$ for
$t=\sqrt{\frac{\gamma\log\frac{N}{\mathcal{I}_{r}r^{2}\log\frac{1}{\delta}}}{\mathcal{I}_{r}r^{2}}}$.
Then, we have

$\operatorname*{\mathbb{E}}_{x\sim
f_{r}}[(\tilde{s}_{r}(x)-s_{r}(x))^{2}\mathbbm{1}_{x\in
S}]\lesssim\frac{\mathcal{I}_{r}}{\gamma}$

######  Proof B.26.

First, by Lemma B.15,

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[s_{r}(x)^{2}\mathbbm{1}_{x\in S}\right]$
$\displaystyle\lesssim\frac{1}{t^{2}r^{2}}\log t^{2}$
$\displaystyle\leq\frac{\mathcal{I}_{r}}{\gamma\log\frac{N}{\mathcal{I}_{r}r^{2}\log\frac{1}{\delta}}}\log\left(\frac{\gamma}{\mathcal{I}_{r}r^{2}}\log\frac{N}{\mathcal{I}_{r}r^{2}\log\frac{1}{\delta}}\right)$
$\displaystyle\lesssim\frac{\mathcal{I}_{r}}{\gamma}\quad\text{since
$\gamma\geq 1$, $\gamma\leq\frac{N}{\log\frac{1}{\delta}}$ and
$\mathcal{I}_{r}\leq\frac{1}{r^{2}}$}$

Now, by assumption,

$|\tilde{s}_{r}(x)|\leq\frac{2}{r}\sqrt{\log\frac{N}{\log\frac{1}{\delta}}}$

So,

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[\tilde{s}_{r}(x)^{2}\mathbbm{1}_{x\in S}\right]$
$\displaystyle\leq\frac{4}{t^{2}r^{2}}\log\frac{N}{\log\frac{1}{\delta}}$
$\displaystyle=\frac{\mathcal{I}_{r}}{\gamma\log\frac{N}{\mathcal{I}_{r}r^{2}\log\frac{1}{\delta}}}\log\left(\frac{N}{\log\frac{1}{\delta}}\right)$
$\displaystyle\lesssim\frac{\mathcal{I}_{r}}{\gamma\log\frac{N}{\mathcal{I}_{r}r^{2}\log\frac{1}{\delta}}}\log\left(\frac{N}{\mathcal{I}_{r}r^{2}\log\frac{1}{\delta}}\right)\quad\text{since
$\mathcal{I}_{r}\leq\frac{1}{r^{2}}$}$
$\displaystyle\lesssim\frac{\mathcal{I}_{r}}{\gamma}$

Thus, we have

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[(\tilde{s}_{r}(x)-s_{r}(x))^{2}\mathbbm{1}_{x\in S}\right]$
$\displaystyle\lesssim\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[\tilde{s}_{r}(x)^{2}\mathbbm{1}_{x\in
S}\right]+\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[s_{r}(x)^{2}\mathbbm{1}_{x\in S}\right]$
$\displaystyle\lesssim\frac{\mathcal{I}_{r}}{\gamma}$

The next lemma shows that within the typical $t\sigma$ radius around the mean,
for the set of points with small density, the clipped KDE score
$\widehat{s}_{r}^{\text{clip}}$ approximates the true score $s_{r}$ well.

######  Lemma B.27 (Error estimate over small density regions within typical
region).

Let $f^{*}$ be an arbitrary distribution with mean $\mu$ and variance
$\sigma^{2}$, and let $f_{r}$ be the $r$-smoothed version of $f^{*}$, with
variance $\sigma_{r}^{2}=\sigma^{2}+r^{2}$. Let $s_{r}$ be the score function
of $f_{r}$, and let $\mathcal{I}_{r}$ be the Fisher information. Let
$\tilde{s}_{r}$ be any score function with
$|\tilde{s}_{r}(x)|\leq\frac{2}{r}\sqrt{\log\frac{N}{\log\frac{1}{\delta}}}$
for all $x$. Let
$t=\sqrt{\frac{\gamma\log\frac{N}{\mathcal{I}_{r}r^{2}\log\frac{1}{\delta}}}{\mathcal{I}_{r}r^{2}}}$
for $\gamma\geq 1$, and let $\alpha=\frac{1}{t^{3}\sigma_{r}}$. Then,

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim
f_{r}}[(\tilde{s}_{r}(x)-s_{r}(x))^{2}\mathbbm{1}_{\\{|x-\mu|\leq
t\sigma_{r}\text{ and }f(x)<\alpha\\}}]\lesssim\frac{\mathcal{I}_{r}}{\gamma}$

######  Proof B.28.

By our choice of $\alpha$,

$\Pr_{x\sim f_{r}}[|x-\mu|\leq t\sigma_{r}\text{ and }f(x)<\alpha]\leq\alpha
t\sigma_{r}=\frac{1}{t^{2}}$

So, by Lemma B.25, the claim follows

The next lemma shows that in the region outside the typical region of radius
$t\sigma$ around the true mean, the clipped KDE score
$\widehat{s}_{r}^{\text{clip}}$ approximates the true score well.

######  Lemma B.29 (Error estimate over atypical region).

Let $f^{*}$ be an arbitrary distribution with mean $\mu$ and variance
$\sigma^{2}$, and let $f_{r}$ be the $r$-smoothed version of $f^{*}$, with
variance $\sigma_{r}^{2}=\sigma^{2}+r^{2}$. Let $s_{r}$ be the score function
of $f_{r}$, and let $\mathcal{I}_{r}$ be the Fisher information. Let
$\tilde{s}_{r}$ be any score function with
$|\tilde{s}_{r}(x)|\leq\frac{2}{r}\sqrt{\log\frac{N}{\log\frac{1}{\delta}}}$
for all $x$. Let
$t=\sqrt{\frac{\gamma\log\frac{N}{\mathcal{I}_{r}r^{2}\log\frac{1}{\delta}}}{\mathcal{I}_{r}r^{2}}}$
for $\gamma\geq 1$, and let $\alpha=\frac{1}{t^{3}\sigma}$. Then,

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim
f_{r}}[(\tilde{s}_{r}(x)-s_{r}(x))^{2}\mathbbm{1}_{|x-\mu|>t\sigma_{r}}]\lesssim\frac{\mathcal{I}_{r}}{\gamma}$

######  Proof B.30.

By Chebyshev’s inequality,

$\Pr[|x-\mu|>t\sigma_{r}]\leq\frac{1}{t^{2}}$

So, by Lemma B.25, the claim follows.

The main result of this section as follows shows that the clipped KDE score
approximates the true score well. See 4.1

######  Proof B.31.

Let $\mu,\sigma_{r}^{2}$ be the mean and variance of $f_{r}$. Let
$t=\sqrt{\frac{\gamma\log\frac{N}{\mathcal{I}_{r}r^{2}\log\frac{1}{\delta}}}{\mathcal{I}_{r}r^{2}}}$,
$\alpha=\frac{1}{t^{3}\sigma_{r}}$. Now,

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[(\widehat{s}_{r}^{\text{clip}}(x)-s_{r}(x))^{2}\right]$
$\displaystyle=\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[(\widehat{s}_{r}^{\text{clip}}(x)-s_{r}(x))^{2}\mathbbm{1}_{\\{|x-\mu|\leq
t\sigma_{r}\text{ and }f_{r}(x)\geq\alpha\\}}\right]$
$\displaystyle\quad+\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[(\widehat{s}_{r}^{\text{clip}}(x)-s_{r}(x))^{2}\mathbbm{1}_{\\{|x-\mu|\leq
t\sigma_{r}\text{ and }f_{r}(x)<\alpha\\}}\right]$
$\displaystyle\quad+\operatorname*{\mathbb{E}}_{x\sim
f_{r}}[(\widehat{s}_{r}^{\text{clip}}(x)-s_{r}(x))^{2}\mathbbm{1}_{|x-\mu|>t\sigma_{r}}]$

So, by Lemmas B.23, B.27 and B.29, we have the claim.

##  Appendix C Symmetrization

In this section we show that the expectation of our symmetrized, clipped KDE
score function $\widehat{s}_{r}^{\text{sym}}$, symmetrized around a point
$\mu+\varepsilon$ for small $\varepsilon$ has expectation close to
$\varepsilon\mathcal{I}_{r}$, where $\mathcal{I}_{r}$ is the Fisher
information of the $r$-smoothed distribution. We also show that the second
moment of $\widehat{s}_{r}^{\text{sym}}$ is close to $\mathcal{I}_{r}$. We
begin by recalling the definition of $\widehat{s}_{r}^{\text{sym}}$ from (7).

#### Definition

Let the symmetrized, clipped KDE score, symmetrized around a point $y$ from
$N$ samples be given by

$\widehat{s}_{r}^{\text{sym}}(x)=\begin{cases}\widehat{s}_{r}^{\text{clip}}(x)&x\geq
y\\\ -\widehat{s}_{r}^{\text{clip}}(2y-x)&x<y\end{cases}$ (12)

where $\widehat{s}_{r}^{\text{clip}}$ is the clipped KDE score from $N$
samples, as defined in (9).

First we show that the true score function centered at $-\varepsilon$ is close
to the true score centered at $0$ in $\ell_{2}$ distance.

######  Lemma C.1.

Let $f_{r}$ be an $r$-smoothed distribution with score function $s_{r}$ and
Fisher information $\mathcal{I}_{r}$. Then, for $|\varepsilon|\leq r/60$,

$\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[(s_{r}(x+\varepsilon)-s_{r}(x))^{2}\right]\lesssim\frac{\varepsilon^{2}}{r^{4}}$

######  Proof C.2.

By Lemma G.7,

$\displaystyle\begin{split}s_{r}(x+\varepsilon)-s_{r}(x)&=\frac{\operatorname*{\mathbb{E}}_{Z_{r}|x}\left[e^{\frac{\varepsilon
Z_{r}}{r^{2}}}\frac{Z_{r}-\varepsilon}{r^{2}}\right]}{\operatorname*{\mathbb{E}}_{Z_{r}|x}\left[e^{\frac{\varepsilon
Z_{r}}{r^{2}}}\right]}-\operatorname*{\mathbb{E}}_{Z_{r}|x}\left[\frac{Z_{r}}{r^{2}}\right]\\\
&=-\frac{\varepsilon}{r^{2}}+\frac{\operatorname*{\mathbb{E}}_{Z_{r}|x}\left[e^{\frac{\varepsilon
Z_{r}}{r^{2}}}(Z_{r}-\operatorname*{\mathbb{E}}_{Z_{r}|x}[Z_{r}])\right]}{r^{2}\operatorname*{\mathbb{E}}_{Z_{r}|x}\left[e^{\frac{\varepsilon
Z_{r}}{r^{2}}}\right]}\end{split}$ (13)

Now,

$\displaystyle\operatorname*{\mathbb{E}}_{Z_{r}|x}\left[e^{\frac{\varepsilon
Z_{r}}{r^{2}}}(Z_{r}-\operatorname*{\mathbb{E}}_{Z_{r}|x}[Z_{r}])\right]$
$\displaystyle=\operatorname*{\mathbb{E}}_{Z_{r}|x}\left[(e^{\frac{\varepsilon
Z_{r}}{r^{2}}}-1)Z_{r}\right]-\operatorname*{\mathbb{E}}_{Z_{r}|x}\left[e^{\frac{\varepsilon
Z_{r}}{r^{2}}}-1\right]\operatorname*{\mathbb{E}}_{Z_{r}|x}[Z_{r}]$

So,

$\displaystyle\operatorname*{\mathbb{E}}_{Z_{r}|x}\left[e^{\frac{\varepsilon
Z_{r}}{r^{2}}}(Z_{r}-\operatorname*{\mathbb{E}}_{Z_{r}|x}[Z_{r}])\right]^{4}$
$\displaystyle\lesssim\operatorname*{\mathbb{E}}_{Z_{r}|x}\left[(e^{\frac{\varepsilon
Z_{r}}{r^{2}}}-1)Z_{r}\right]^{4}+\operatorname*{\mathbb{E}}_{Z_{r}|x}\left[e^{\frac{\varepsilon
Z_{r}}{r^{2}}}-1\right]^{4}\operatorname*{\mathbb{E}}_{Z_{r}|x}[Z_{r}]^{4}$
$\displaystyle\lesssim\operatorname*{\mathbb{E}}_{Z_{r}|x}\left[(e^{\frac{\varepsilon
Z_{r}}{r^{2}}}-1)^{4}\right]\operatorname*{\mathbb{E}}_{Z_{r}|x}[Z_{r}^{4}]\quad\text{by
Cauchy-Schwarz and Jensen's inequalities}$

So, we have, by Cauchy-Schwarz and Jensen’s inequalities,

$\displaystyle\operatorname*{\mathbb{E}}_{x}\left[\operatorname*{\mathbb{E}}_{Z_{r}|x}\left[e^{\frac{\varepsilon
Z_{r}}{r^{2}}}(Z_{r}-\operatorname*{\mathbb{E}}_{Z_{r}|x}[Z_{r}])\right]^{4}\right]$
$\displaystyle\lesssim\sqrt{\operatorname*{\mathbb{E}}_{Z_{r}}\left[(e^{\frac{\varepsilon
Z_{r}}{r^{2}}}-1)^{8}\right]\operatorname*{\mathbb{E}}_{Z_{r}}\left[Z_{r}^{8}\right]}$
(14)

We will now bound
$\operatorname*{\mathbb{E}}_{Z_{r}}\left[(e^{\frac{\varepsilon
Z_{r}}{r^{2}}}-1)^{8}\right]$. By a Taylor expansion, when $|\varepsilon
z|\leq r^{2}$

$\displaystyle e^{\frac{\varepsilon z}{r^{2}}}-1=\frac{\varepsilon
z}{r^{2}}+O\left(\left(\frac{\varepsilon z}{r^{2}}\right)^{2}\right)$

so that

$\operatorname*{\mathbb{E}}_{Z_{r}\sim\mathcal{N}(0,r^{2})}\left[(e^{\frac{\varepsilon
Z_{r}}{r^{2}}}-1)^{8}\mathbbm{1}_{|\varepsilon Z_{r}|\leq
r^{2}}\right]\lesssim\frac{\varepsilon^{8}}{r^{16}}\operatorname*{\mathbb{E}}_{Z_{r}}\left[Z_{r}^{8}\right]\lesssim\frac{\varepsilon^{8}}{r^{8}}$

On the other hand, when $|\varepsilon z|\geq r^{2}$, we have
$(e^{\frac{\varepsilon z}{r^{2}}}-1)^{8}\lesssim e^{\frac{8|\varepsilon
z|}{r^{2}}}$, meaning that

$\displaystyle\operatorname*{\mathbb{E}}_{Z_{r}\sim\mathcal{N}(0,r^{2})}\left[(e^{\frac{\varepsilon
Z_{r}}{r^{2}}}-1)^{8}\mathbbm{1}_{|\varepsilon Z_{r}|>r^{2}}\right]$
$\displaystyle\lesssim\int_{|r^{2}/\varepsilon|}^{\infty}\frac{1}{\sqrt{2\pi}r}e^{\frac{8|\varepsilon
z|}{r^{2}}}e^{-\frac{z^{2}}{2r^{2}}}dz$
$\displaystyle=e^{\frac{32\varepsilon^{2}}{r^{2}}}\int_{|r^{2}/\varepsilon|}^{\infty}\frac{1}{\sqrt{2\pi}r}e^{-\frac{(z-8|\varepsilon|)^{2}}{2r^{2}}}dz$
$\displaystyle\lesssim\Pr_{Z_{r}\sim\mathcal{N}(0,r^{2})}\left[Z_{r}\geq
r^{2}/|\varepsilon|-8|\varepsilon|\right]$ $\displaystyle\lesssim
e^{-\frac{(|r^{2}/\varepsilon|-8|\varepsilon|)^{2}}{2r^{2}}}$
$\displaystyle\lesssim\frac{\varepsilon^{8}}{r^{8}}$

Also, $\operatorname*{\mathbb{E}}_{Z_{r}}[Z_{r}^{8}]\lesssim r^{8}$ So, we
have shown in (14),

$\displaystyle\operatorname*{\mathbb{E}}_{x}\left[\operatorname*{\mathbb{E}}_{Z_{r}|x}\left[e^{\frac{\varepsilon
Z_{r}}{r^{2}}}(Z_{r}-\operatorname*{\mathbb{E}}_{Z_{r}|x}[Z_{r}])\right]^{4}\right]\lesssim\frac{\varepsilon^{4}}{r^{4}}\sqrt{\operatorname*{\mathbb{E}}_{Z_{r}}[Z_{r}^{8}]}\lesssim\varepsilon^{4}$

Also, using Jensen’s inequality

$\displaystyle\operatorname*{\mathbb{E}}_{x}\left[\frac{1}{\operatorname*{\mathbb{E}}_{Z_{r}|x}\left[e^{\frac{\varepsilon
Z_{r}}{r^{2}}}\right]^{4}}\right]$
$\displaystyle\leq\operatorname*{\mathbb{E}}_{x}\left[e^{-4\varepsilon\operatorname*{\mathbb{E}}_{Z_{r}|x}[Z_{r}/r^{2}]}\right]$
$\displaystyle=\operatorname*{\mathbb{E}}_{x}\left[e^{-4\varepsilon
s_{r}(x)}\right]\quad\text{since
$s_{r}(x)=\operatorname*{\mathbb{E}}_{Z_{r}|x}[Z_{r}]/r^{2}$ by
Lemma\leavevmode\nobreak\ \ref{lem:shifted_score_characterization}}$
$\displaystyle\leq e^{8\varepsilon^{2}/r^{2}}\lesssim 1\quad\text{by
Lemma\leavevmode\nobreak\ \ref{lem:score-subgaussian} and since
$|\varepsilon|\leq r/60$}$

Then, using (13),

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[(s_{r}(x+\varepsilon)-s_{r}(x))^{2}\right]$
$\displaystyle\lesssim\frac{\varepsilon^{2}}{r^{4}}+\frac{1}{r^{4}}\operatorname*{\mathbb{E}}_{x}\left[\frac{\operatorname*{\mathbb{E}}_{Z_{r}|x}\left[e^{\frac{\varepsilon
Z_{r}}{r^{2}}}(Z_{r}-\operatorname*{\mathbb{E}}_{Z_{r}|x}[Z_{r}])\right]^{2}}{\operatorname*{\mathbb{E}}_{Z_{r}|x}[e^{\frac{\varepsilon
Z_{r}}{r^{2}}}]^{2}}\right]$
$\displaystyle\leq\frac{\varepsilon^{2}}{r^{4}}+\frac{1}{r^{4}}\sqrt{\operatorname*{\mathbb{E}}_{x}\left[\operatorname*{\mathbb{E}}_{Z_{r}|x}\left[e^{\frac{\varepsilon
Z_{r}}{r^{2}}}(Z_{r}-\operatorname*{\mathbb{E}}_{Z_{r}|x}[Z_{r}])\right]^{4}\right]\operatorname*{\mathbb{E}}_{x}\left[\frac{1}{\operatorname*{\mathbb{E}}_{Z_{r}|x}\left[e^{\frac{\varepsilon
Z_{r}}{r^{2}}}\right]^{4}}\right]}$
$\displaystyle\lesssim\frac{\varepsilon^{2}}{r^{4}}$

The next lemma shows that $\widehat{s}_{r}^{\text{sym}}$ approximates $s_{r}$
in a certain sense. Using this, we obtain that the second moment of
$\widehat{s}_{r}^{\text{sym}}$ is close the $\mathcal{I}_{r}$.

######  Lemma C.3.

Let $f^{*}$ be an arbitrary symmetric distribution with mean $\mu$, and let
$f_{r}$ be the $r$-smoothed version of $f^{*}$. Let $s_{r}$ be the score
function of $f_{r}$, and let $\mathcal{I}_{r}$ be the Fisher information. Let
$\widehat{s}_{r}^{\text{sym}}$ be the symmetrized clipped Kernel Density
Estimate score from $N$ samples, symmetrized around $\mu+\varepsilon$ for
$|\varepsilon|\leq r/60$, as defined in (12). Let $\gamma>C$ be a parameter
for large enough constant $C$. Then for any $r\leq\sigma$ and
$\frac{N}{\log\frac{1}{\delta}}\geq\left(\frac{\gamma^{5/12}\sigma}{r}\right)^{6+\beta}$
for $\beta>0$, if $|\varepsilon|\leq
r^{2}\sqrt{\frac{\mathcal{I}_{r}}{\gamma}}$, with probability $1-\delta$,

$\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[(\widehat{s}_{r}^{\text{sym}}(x)-s_{r}(x))^{2}\right]\lesssim\frac{\mathcal{I}_{r}}{\gamma}$

######  Proof C.4.

By definition of $\widehat{s}_{r}^{\text{sym}}$, and using Lemma 4.1,

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[(\widehat{s}_{r}^{\text{sym}}(x)-s_{r}(x))^{2}\mathbbm{1}_{x\geq\mu+\varepsilon}\right]=\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[(\widehat{s}_{r}^{\text{clip}}(x)-s_{r}(x))^{2}\mathbbm{1}_{x\geq\mu+\varepsilon}\right]\lesssim\frac{\mathcal{I}_{r}}{\gamma}$

On the other hand, by Lemmas 4.1 and C.1

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[(\widehat{s}_{r}^{\text{sym}}(x)-s_{r}(x))^{2}\mathbbm{1}_{x<\mu+\varepsilon}\right]$
$\displaystyle=\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[(-\widehat{s}_{r}^{\text{clip}}(2(\mu+\varepsilon)-x)+s_{r}(2\mu-x))^{2}\mathbbm{1}_{x<\mu+\varepsilon}\right]$
$\displaystyle\leq\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[(-\widehat{s}_{r}^{\text{clip}}(2(\mu+\varepsilon)-x)+s_{r}(2(\mu+\varepsilon)-x))^{2}\mathbbm{1}_{x<\mu+\varepsilon}\right]+\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[(s_{r}((2\mu-x)+2\varepsilon)-s_{r}(2\mu-x))^{2}\right]$
$\displaystyle\lesssim\frac{\mathcal{I}_{r}}{\gamma}+\frac{\varepsilon^{2}}{r^{4}}$

The claim follows since
$\frac{\varepsilon^{2}}{r^{4}}\leq\frac{\mathcal{I}_{r}}{\gamma}$.

See 4.3

######  Proof C.5.

We have

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[\widehat{s}_{r}^{\text{sym}}(x)^{2}\right]$
$\displaystyle=\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[(s_{r}(x)+\widehat{s}_{r}^{\text{sym}}(x)-s_{r}(x))^{2}\right]$
$\displaystyle=\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[s_{r}(x)^{2}\right]+2\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[s_{r}(x)(\widehat{s}_{r}^{\text{sym}}(x)-s_{r}(x))\right]+\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[(\widehat{s}_{r}^{\text{sym}}(x)-s_{r}(x))^{2}\right]$
$\displaystyle\leq\operatorname*{\mathbb{E}}_{x\sim
f_{r}}[s_{r}(x)^{2}]+2\sqrt{\operatorname*{\mathbb{E}}_{x\sim
f_{r}}[s_{r}(x)^{2}]\operatorname*{\mathbb{E}}_{x\sim
f_{r}}[(\widehat{s}^{\text{sym}}(x)-s_{r}(x))^{2}]}+\operatorname*{\mathbb{E}}_{x\sim
f_{r}}[(\widehat{s}_{r}^{\text{sym}}(x)-s_{r}(x))^{2}]$

So, by Lemma C.3,

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[\widehat{s}_{r}^{\text{sym}}(x)^{2}\right]-\mathcal{I}_{r}$
$\displaystyle\lesssim\frac{\mathcal{I}_{r}}{\sqrt{\gamma}}+\frac{\mathcal{I}_{r}}{\gamma}\lesssim\frac{\mathcal{I}_{r}}{\sqrt{\gamma}}$

Similarly,

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[s_{r}(x)^{2}\right]$
$\displaystyle\leq\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[\widehat{s}_{r}^{\text{sym}}(x)^{2}\right]+2\sqrt{\operatorname*{\mathbb{E}}_{x\sim
f_{r}}[\widehat{s}_{r}^{\text{sym}}(x)^{2}]\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[(\widehat{s}_{r}^{\text{sym}}(x)-s_{r}(x))^{2}\right]}+\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[(\widehat{s}_{r}^{\text{sym}}(x)-s_{r}(x))^{2}\right]$

So, since we showed $\operatorname*{\mathbb{E}}_{x\sim
f_{r}}[\widehat{s}_{r}^{\text{sym}}(x)^{2}]\lesssim\mathcal{I}_{r}$, we have

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim
f_{r}}[s_{r}(x)^{2}]\leq\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[\widehat{s}_{r}^{\text{sym}}(x)^{2}\right]+O\left(\frac{\mathcal{I}_{r}}{\sqrt{\gamma}}\right)$

so that

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[\widehat{s}_{r}^{\text{sym}}(x)^{2}\right]-\mathcal{I}_{r}\gtrsim\frac{\mathcal{I}_{r}}{\sqrt{\gamma}}$

The claim follows.

Finally, we show that the expectation of the symmetrized, clipped KDE score
function $\widehat{s}_{r}^{\text{sym}}$ symmetrized around $\mu+\varepsilon$
for small $\varepsilon$ is close to $\varepsilon\mathcal{I}_{r}$. See 4.5

######  Proof C.6.

Since $f_{r}$ is symmetric around $\mu$, $f_{r}(x)=f_{r}(2\mu-x)$. So using
the definition of $\widehat{s}_{r}^{\text{sym}}$, we have

$\displaystyle\int_{-\infty}^{\mu+\varepsilon}f_{r}(x-\varepsilon)\widehat{s}^{\text{sym}}_{r}(x)dx$
$\displaystyle=-\int_{-\infty}^{\mu+\varepsilon}f_{r}(2\mu-x+\varepsilon)s_{r}^{\text{clip}}(2(\mu+\varepsilon)-x)dx$
$\displaystyle=\int_{\infty}^{\mu+\varepsilon}f_{r}(y-\varepsilon)s_{r}^{\text{clip}}(y)dy\quad\text{Substituting
$y=2(\mu+\varepsilon)-x$}$
$\displaystyle=-\int_{\mu+\varepsilon}^{\infty}f_{r}(y-\varepsilon)s_{r}^{\text{sym}}(y)dy\quad\text{since
$s_{r}^{\text{sym}}(x)=s_{r}^{\text{clip}}(x)$ for $x\geq\mu+\varepsilon$}$

So, we have

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[\frac{f_{r}(x-\varepsilon)}{f_{r}(x)}\widehat{s}_{r}^{\text{sym}}(x)\right]=\int_{-\infty}^{\mu+\varepsilon}f_{r}(x-\varepsilon)\widehat{s}_{r}^{\text{sym}}(x)dx+\int_{\mu+\varepsilon}^{\infty}f_{r}(x-\varepsilon)s_{r}^{\text{sym}}(x)dx=0$

So,

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[\widehat{s}_{r}^{\text{sym}}(x)\right]=\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[\frac{f_{r}(x)-f_{r}(x-\varepsilon)}{f_{r}(x)}\widehat{s}_{r}^{\text{sym}}(x)\right]$

Thus,

$\displaystyle\left(\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[\widehat{s}_{r}^{\text{sym}}(x)\right]-\varepsilon\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[\widehat{s}_{r}^{\text{sym}}(x)^{2}\right]\right)^{2}$
$\displaystyle=\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[\left(\frac{f_{r}(x)-f_{r}(x-\varepsilon)}{f_{r}(x)}-\varepsilon\widehat{s}_{r}^{\text{sym}}(x)\right)\widehat{s}_{r}^{\text{sym}}(x)\right]^{2}$
$\displaystyle=\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[\left(\frac{f_{r}(x)-f_{r}(x-\varepsilon)-\varepsilon
f_{r}^{\prime}(x)}{f_{r}(x)}+\varepsilon(s_{r}(x)-\widehat{s}_{r}^{\text{sym}}(x))\right)\widehat{s}_{r}^{\text{sym}}(x)\right]^{2}\quad\text{since
$s_{r}(x)=\frac{f_{r}^{\prime}(x)}{f_{r}(x)}$}$
$\displaystyle\leq\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[\left(\frac{f_{r}(x)-f_{r}(x-\varepsilon)-\varepsilon
f_{r}^{\prime}(x)}{f_{r}(x)}+\varepsilon(s_{r}(x)-\widehat{s}_{r}^{\text{sym}}(x))\right)^{2}\right]\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[\widehat{s}_{r}^{\text{sym}}(x)^{2}\right]$
$\displaystyle\lesssim\left(\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[\left(\frac{f_{r}(x)-f_{r}(x-\varepsilon)-\varepsilon
f_{r}^{\prime}(x)}{f_{r}(x)}\right)^{2}\right]+\varepsilon^{2}\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[(s_{r}(x)-\widehat{s}_{r}^{\text{sym}}(x))^{2}\right]\right)\operatorname*{\mathbb{E}}_{x\sim
f_{r}}[\widehat{s}_{r}^{\text{sym}}(x)^{2}]$
$\displaystyle=\left(\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[\Delta_{-\varepsilon}(x)^{2}\right]+\varepsilon^{2}\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[(s_{r}(x)-\widehat{s}_{r}^{\text{sym}}(x))^{2}\right]\right)\operatorname*{\mathbb{E}}_{x\sim
f_{r}}[\widehat{s}_{r}^{\text{sym}}(x)^{2}]$

where $\Delta_{\varepsilon}(x)=\frac{f_{r}(x+\varepsilon)-f_{r}(x)-\varepsilon
f_{r}^{\prime}(x)}{f_{r}(x)}$. But by Lemma G.11,
$\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[\Delta_{-\varepsilon}(x)^{2}\right]\lesssim\frac{\varepsilon^{4}}{r^{4}}\lesssim\varepsilon^{2}\frac{\mathcal{I}_{r}}{\gamma}$
(since $|\varepsilon|\leq r^{2}\sqrt{\frac{\mathcal{I}_{r}}{\gamma}}$). So, by
Lemma C.3 and Lemma 4.3, we have

$\displaystyle\left|\operatorname*{\mathbb{E}}_{x\sim
f_{r}}[\widehat{s}_{r}^{\text{sym}}(x)]-\varepsilon\operatorname*{\mathbb{E}}_{x\sim
f_{r}}[\widehat{s}_{r}^{\text{sym}}(x)^{2}]\right|$
$\displaystyle\lesssim\sqrt{\left(\varepsilon^{2}\frac{\mathcal{I}_{r}}{\gamma}+\varepsilon^{2}\frac{\mathcal{I}_{r}}{\gamma}\right)\mathcal{I}_{r}}$
$\displaystyle\lesssim\frac{\varepsilon\mathcal{I}_{r}}{\sqrt{\gamma}}$

Then, using Lemma 4.3 once again on $\operatorname*{\mathbb{E}}_{x\sim
f_{r}}[s_{r}^{\text{sym}}(x)^{2}]$ on the LHS, the claim follows.

##  Appendix D Estimating $\mathcal{I}_{r}$

In this section, we show that
$\widehat{\mathcal{I}}_{r}=\operatorname*{\mathbb{E}}_{x\sim\widehat{f}_{r}}[\widehat{s}_{r}^{\text{sym}}(x)^{2}]$
provides a good estimate of $\mathcal{I}_{r}$.

######  Lemma D.1.

Let $\widehat{f}_{r}$ be the kernel density estimate of $f_{r}$ from $N$
samples $Y_{1},\dots,Y_{N}\sim f^{*}$ as defined in (8). Let $x,\varepsilon,N$
be such that $N\geq\frac{12\log\frac{2}{\delta}}{f_{r}(x)r}$ and
$\frac{16|\varepsilon|}{r}\sqrt{\log\frac{1}{rf_{r}(x)}}\leq 1$. We have that
with probability $1-\delta$, for all $|\zeta|\leq|\varepsilon|$
simultaneously,

$\displaystyle|\widehat{f}_{r}(x+\zeta)-f_{r}(x+\zeta)|\lesssim\sqrt{\frac{f_{r}(x+\zeta)\log\frac{2}{\delta}}{Nr}}+\frac{|\varepsilon|f_{r}(x+\zeta)}{r}\sqrt{\log\frac{2}{f_{r}(x+\zeta)r}}$

######  Proof D.2.

By Lemma B.1, with probability $1-\delta$,

$|\widehat{f}_{r}(x)-f_{r}(x)|\leq\sqrt{\frac{3f_{r}(x)\log\frac{2}{\delta}}{Nr}}$

Note that since $N\geq\frac{12\log\frac{2}{\delta}}{f_{r}(x)r}$, the RHS above
is at most $\frac{f_{r}(x)}{2}$.

Also, by Lemma B.9,

$\displaystyle|f_{r}(x+\zeta)-f_{r}(x)|\leq\frac{10|\varepsilon|f_{r}(x)}{r}\sqrt{\log\frac{1}{f_{r}(x)r}}$

Now, since
$\frac{8|\varepsilon|}{r}\sqrt{\log\frac{1}{r\widehat{f}_{r}(x)}}\leq\frac{8|\varepsilon|}{r}\sqrt{\log\frac{2}{rf_{r}(x)}}\leq\frac{16|\varepsilon|}{r}\sqrt{\log\frac{1}{rf_{r}(x)}}<1$,
by Lemma B.9,

$\displaystyle|\widehat{f}_{r}(x+\zeta)-\widehat{f}_{r}(x)|$
$\displaystyle\leq\frac{10|\varepsilon|\widehat{f}_{r}(x)}{r}\sqrt{\log\frac{1}{\widehat{f}_{r}(x)r}}$
$\displaystyle\leq\frac{15|\varepsilon|f_{r}(x)}{r}\sqrt{\log\frac{2}{f_{r}(x)r}}$

So, putting everything together

$\displaystyle|\widehat{f}_{r}(x+\zeta)-f_{r}(x+\zeta)|$
$\displaystyle\leq|\widehat{f}_{r}(x+\zeta)-\widehat{f}_{r}(x)|+|\widehat{f}_{r}(x)-f_{r}(x)|+|f_{r}(x)-f_{r}(x+\zeta)|$
$\displaystyle\leq\sqrt{\frac{3f_{r}(x)\log\frac{2}{\delta}}{Nr}}+\frac{30|\varepsilon|f_{r}(x)}{r}\sqrt{\log\frac{2}{f_{r}(x)r}}$

Now, since $\frac{16|\varepsilon|}{r}\sqrt{\log\frac{1}{rf_{r}(x)}}\leq 1$ so
that by Lemma B.9

$|f_{r}(x+\zeta)-f_{r}(x)|\leq\frac{5}{8}f_{r}(x)$

The claim follows.

######  Lemma D.3.

Let $f^{*}$ be an arbitrary distribution with mean $\mu$ and variance
$\sigma^{2}$ and let $f_{r}$ be the $r$-smoothed version of $f^{*}$, with
variance $\sigma_{r}^{2}=\sigma^{2}+r^{2}$. Let $\widehat{f}_{r}$ be the
kernel density estimate of $f_{r}$ from $N$ samples $Y_{1},\dots,Y_{N}\sim
f^{*}$ as defined in (8). Let $0<\alpha\leq\frac{1}{\sqrt{2\pi}r}$ and let
$N\geq\frac{12\log\left(\frac{2}{\delta}\left(\frac{2t\sigma_{r}\sqrt{\alpha
N}}{\sqrt{r}}+1\right)\right)+400\log\frac{1}{\alpha r}}{\alpha r}$. Then,
with probability $1-\delta$, for all $x$ such that $|x-\mu|\leq t\sigma_{r}$
and $f_{r}(x)\geq\alpha$ simultaneously,

$\displaystyle|\widehat{f}_{r}(x)-f_{r}(x)|\lesssim
f_{r}(x)\sqrt{\frac{1}{\alpha
rN}\log\left(\frac{2}{\delta}\left(\frac{2t\sigma_{r}\sqrt{\alpha
N}}{\sqrt{r}}+1\right)\right)\log\frac{2}{\alpha r}}$

######  Proof D.4.

Consider contiguous intervals of length $\varepsilon$ starting from
$\mu-t\sigma_{r}$ so that the last interval covers $\mu+t\sigma_{r}$, and let
$S$ be the set of the smallest $y$ such that $f_{r}(y)\geq\alpha$ in each of
these intervals, if one exists. Note that
$|S|\leq\frac{2t\sigma_{r}}{\varepsilon}+1$. Then, we have that

$\displaystyle\\{x:|x-\mu|\leq t\sigma_{r}\text{ and
}f_{r}(x)\geq\alpha\\}\subseteq\\{[y-\varepsilon,y+\varepsilon]|y\in S\\}$

Now for $\varepsilon=\sqrt{\frac{r}{\alpha N}}$ and $y\in S$, since
$N\geq\frac{12\log\left(\frac{2}{\delta}\left(\frac{2t\sigma_{r}\sqrt{\alpha
N}}{\sqrt{r}}+1\right)\right)}{\alpha
r}\geq\frac{12\log\frac{2|S|}{\delta}}{f_{r}(y)r}$ and
$\frac{16|\varepsilon|}{r}\sqrt{\log\frac{1}{rf_{r}(y)}}=\frac{16}{\sqrt{\alpha
rN}}\sqrt{\log\frac{1}{f_{r}(y)r}}\leq\frac{16}{\sqrt{\alpha
rN}}\sqrt{\log\frac{1}{\alpha r}}\leq 1$, we have by Lemma D.1 that with
probability $1-\frac{\delta}{|S|}$, for all $|\zeta|\leq|\varepsilon|$
simultaneously,

$\displaystyle\left|\widehat{f}_{r}(y+\zeta)-f_{r}(y+\zeta)\right|$
$\displaystyle\lesssim\sqrt{\frac{f_{r}(y+\zeta)\log\frac{2|S|}{\delta}}{Nr}}+f_{r}(y+\zeta)\sqrt{\frac{1}{\alpha
Nr}\log\frac{2}{\alpha r}}$ $\displaystyle\lesssim
f_{r}(y+\zeta)\sqrt{\frac{1}{\alpha
Nr}\log\left(\frac{2}{\delta}\left(\frac{2t\sigma_{r}\sqrt{\alpha
N}}{\sqrt{r}}+1\right)\right)\log\frac{2}{\alpha r}}$ since
$f_{r}(y+\zeta)\gtrsim\alpha$ and $\alpha\leq\frac{1}{\sqrt{2\pi}r}$ so that
$\log\frac{2}{\alpha r}>1$

So by a union bound, with probability $1-\delta$, for all $x$ such that
$|x-\mu|\leq t\sigma_{r}$ and $f_{r}(x)\geq\alpha$ simultaneously,

$\displaystyle|\widehat{f}_{r}(x)-f_{r}(x)|\lesssim
f_{r}(x)\sqrt{\frac{1}{\alpha
Nr}\log\left(\frac{2}{\delta}\left(\frac{2t\sigma_{r}\sqrt{\alpha
N}}{\sqrt{r}}+1\right)\right)\log\frac{2}{\alpha r}}$

######  Lemma D.5.

Let $S$ be a set and let $\widehat{f}_{r}$ be the kernel density estimate of
$f_{r}$ from $N$ samples $Y_{1},\dots,Y_{N}\sim f^{*}$. Then, with probability
$1-\delta$,

$\left|\Pr_{\widehat{f}_{r}}[S]-\Pr_{f_{r}}[S]\right|\lesssim\sqrt{\frac{\log\frac{2}{\delta}}{N}}$

######  Proof D.6.

$\displaystyle\operatorname*{\mathbb{E}}_{Y_{i}}\left[\left[\Pr_{\widehat{f}_{r}}[S]\right]\right]=\operatorname*{\mathbb{E}}_{Y_{i}}\left[\int_{S}\widehat{f}_{r}(x)dx\right]=\int_{S}\operatorname*{\mathbb{E}}_{Y_{i}}\left[\widehat{f}_{r}(x)\right]dx=\int_{S}f_{r}(x)dx=\Pr_{f_{r}}[S]$

Furthermore $0\leq\Pr_{\widehat{f}_{r}}\left[S\right]\leq 1$. So, by
Hoeffding’s inequality, with probability $1-\delta$,

$\displaystyle\left|\Pr_{\widehat{f}_{r}}[S]-\Pr_{f_{r}}[S]\right|\lesssim\sqrt{\frac{\log\frac{2}{\delta}}{N}}$

######  Lemma D.7.

Let $\gamma\geq C$ for large enough constant $C$, and let
$\frac{N}{\log\frac{1}{\delta}}\geq\left(\frac{\gamma}{r^{4}\mathcal{I}_{r}^{2}}\right)^{1+\alpha}$
for small constant $\alpha>0$. Let $\tilde{s}$ be any function with
$|\tilde{s}_{r}(x)|\leq\frac{2}{r}\sqrt{\log\frac{N}{\log\frac{1}{\delta}}}$
for all $x$. Let $S$ be a set with $\Pr_{f_{r}}[S]\lesssim\frac{1}{t^{2}}$ for
$t=\gamma^{1/4}\sqrt{\frac{\log\frac{N}{\mathcal{I}_{r}r^{2}\log\frac{1}{\delta}}}{\mathcal{I}_{r}r^{2}}}$.
Let $\widehat{f}_{r}$ be the Kernel density estimate of $f_{r}$ as defined in
(8) from $N$ samples. Then, we have

$\displaystyle\int_{S}\left(\widehat{f}_{r}(x)-f_{r}(x)\right)\tilde{s}_{r}(x)^{2}dx\lesssim\frac{\mathcal{I}_{r}}{\sqrt{\gamma}}$

######  Proof D.8.

Since
$|\tilde{s}_{r}(x)|\leq\frac{2}{r}\sqrt{\log\frac{N}{\log\frac{1}{\delta}}}$
and $\Pr_{f_{r}}[S]\leq\frac{1}{t^{2}}$, we have

$\displaystyle\int_{S}\left(\widehat{f}_{r}(x)-f_{r}(x)\right)\tilde{s}_{r}(x)^{2}dx$
$\displaystyle\leq\int_{S}\widehat{f}_{r}(x)\tilde{s}_{r}(x)^{2}dx$
$\displaystyle\leq\frac{4}{r^{2}}\log\left(\frac{N}{\log\frac{1}{\delta}}\right)\Pr_{\widehat{f}_{r}}[S]$
$\displaystyle\lesssim\frac{4}{r^{2}}\log\left(\frac{N}{\log\frac{1}{\delta}}\right)\left(\Pr_{f_{r}}[S]+\sqrt{\frac{\log\frac{2}{\delta}}{N}}\right)\quad\text{by
Lemma\leavevmode\nobreak\ \ref{lem:kde_density_hoeffding}}$
$\displaystyle\lesssim\frac{1}{t^{2}r^{2}}\log\left(\frac{N}{\log\frac{1}{\delta}}\right)+\frac{1}{r^{2}}\sqrt{\frac{\log\frac{1}{\delta}}{N}}\log\left(\frac{N}{\log\frac{1}{\delta}}\right)$

Now,

$\displaystyle\frac{1}{t^{2}r^{2}}\log\frac{N}{\log\frac{1}{\delta}}$
$\displaystyle=\frac{\mathcal{I}_{r}}{\sqrt{\gamma}\log\frac{N}{\mathcal{I}_{r}r^{2}\log\frac{1}{\delta}}}\log\left(\frac{N}{\log\frac{1}{\delta}}\right)\quad\text{by
our setting of $t$}$
$\displaystyle\lesssim\frac{\mathcal{I}_{r}}{\sqrt{\gamma}\log\frac{N}{\mathcal{I}_{r}r^{2}\log\frac{1}{\delta}}}\log\left(\frac{N}{\mathcal{I}_{r}r^{2}\log\frac{1}{\delta}}\right)\quad\text{since
$\mathcal{I}_{r}\leq\frac{1}{r^{2}}$}$
$\displaystyle\lesssim\frac{\mathcal{I}_{r}}{\sqrt{\gamma}}$

Also,

$\displaystyle\frac{1}{r^{2}}\sqrt{\frac{\log\frac{2}{\delta}}{N}}\log\left(\frac{N}{\log\frac{1}{\delta}}\right)$
$\displaystyle\leq\frac{1}{r^{2}}\left(\frac{\log\frac{2}{\delta}}{N}\right)^{\frac{1}{2}-\frac{\alpha}{4}}$
$\displaystyle\lesssim\frac{\mathcal{I}_{r}}{\sqrt{\gamma}}\quad\text{since
$\frac{N}{\log\frac{2}{\delta}}\geq\left(\frac{\gamma}{r^{4}\mathcal{I}_{r}^{2}}\right)^{1+\alpha}$}$

So, the claim follows.

######  Lemma D.9.

Let $\widehat{f}_{r}$ be the kernel density estimate of $f_{r}$ from $N$
samples, as defined in (8). Let $\gamma\geq C$ for large constant $C\geq 1$ be
a parameter. Suppose $\tilde{s}_{r}$ is a function such that
$\operatorname*{\mathbb{E}}_{x\sim
f_{r}}[\tilde{s}_{r}(x)]\lesssim\mathcal{I}_{r}$. Let
$t=\gamma^{1/4}\sqrt{\frac{\log\frac{N}{\mathcal{I}_{r}r^{2}\log\frac{1}{\delta}}}{\mathcal{I}_{r}r^{2}}}$,
$\alpha=\frac{1}{t^{3}\sigma_{r}}$. Then for any $r\leq\sigma$ and
$\frac{N}{\log\frac{1}{\delta}}\geq\left(\gamma^{5/12}\frac{\sigma}{r}\right)^{6+\beta}$
for some small constant $\beta>0$, with probability $1-\delta$, we have

$\displaystyle\int_{-\infty}^{\infty}\left|\widehat{f}_{r}(x)-f_{r}(x)\right|\tilde{s}_{r}(x)^{2}\mathbbm{1}_{\\{|x-\mu|\leq
t\sigma_{r}\text{ and
}f_{r}(x)\geq\alpha\\}}dx\lesssim\frac{\mathcal{I}_{r}}{\sqrt{\gamma}}$

######  Proof D.10.

This proof is similar to the proof of Lemma B.21. First note that since
$r\leq\sigma$,

$\sigma_{r}^{2}=\sigma^{2}+r^{2}\leq 2\sigma^{2}$

Note also that $\frac{N}{\log\frac{1}{\delta}}\geq 1$ since $\gamma\geq 1$ and
$r\leq\sigma$. So our setting of $N$ implies WLOG

$\displaystyle\frac{N}{\log\frac{1}{\delta}}\geq\left(\frac{\gamma^{5/12}\sigma\log\frac{N}{\log\frac{1}{\delta}}}{r}\right)^{6}$

or

$\displaystyle\frac{\sigma}{r}\leq\left(\frac{N}{\log\frac{1}{\delta}}\right)^{1/6}\cdot\frac{1}{\gamma^{5/12}\log\frac{N}{\log\frac{1}{\delta}}}\leq\left(\frac{N}{\log\frac{1}{\delta}}\right)^{1/6}$
(15)

We will first check that this $N$ satisfies the condition required to invoke
Lemma D.3 that
$N\geq\frac{12\log\left(\frac{2}{\delta}\left(\frac{2t\sigma_{r}\sqrt{\alpha
N}}{\sqrt{r}}+1\right)\right)+400\log\frac{1}{\alpha r}}{\alpha r}$. To do
this, we individually upper bound $\frac{1}{\alpha r}$ and
$\frac{2t\sigma_{r}\sqrt{\alpha N}}{\sqrt{r}}$. We have,

$\displaystyle\frac{1}{\alpha r}$
$\displaystyle=\frac{\sigma_{r}\gamma^{3/4}}{r}\left(\frac{\log\frac{N}{\mathcal{I}_{r}r^{2}\log\frac{1}{\delta}}}{\mathcal{I}_{r}r^{2}}\right)^{3/2}\quad\text{since
$\alpha=\frac{1}{t^{3}\sigma_{r}}$ and
$t=\gamma^{1/4}\sqrt{\frac{\log\frac{N}{\mathcal{I}_{r}r^{2}\log\frac{1}{\delta}}}{\mathcal{I}_{r}r^{2}}}$}$
$\displaystyle\leq\left(\frac{\sigma_{r}}{r}\right)^{4}\gamma^{3/4}\log^{3/2}\frac{N\sigma_{r}^{2}}{r^{2}\log\frac{1}{\delta}}\quad\text{since
$\mathcal{I}_{r}\geq\frac{1}{\sigma_{r}^{2}}$}$
$\displaystyle\leq\left(\frac{2\sigma}{r}\right)^{4}\gamma^{3/4}\log^{3/2}\frac{2N\sigma^{2}}{r^{2}\log\frac{1}{\delta}}\quad\text{since
$\sigma_{r}^{2}\leq 2\sigma^{2}$}$ $\displaystyle\leq
16\frac{N^{4/6}}{\gamma^{5/3}\log^{4}\frac{N}{\log\frac{1}{\delta}}\log^{4/6}\frac{1}{\delta}}\cdot\gamma^{3/4}\log^{3/2}\left(2\left(\frac{N}{\log\frac{1}{\delta}}\right)^{4/3}\right)\quad\text{by
\eqref{eq:sigma_over_r_density}}$
$\displaystyle\leq\frac{16N}{\gamma^{5/2}\log^{4}\frac{N}{\log\frac{1}{\delta}}\log\frac{1}{\delta}}\gamma^{3/4}\log^{3/2}\left(2\left(\frac{N}{\log\frac{1}{\delta}}\right)^{4/3}\right)\quad\text{since
$\frac{N}{\log\frac{1}{\delta}}\geq\gamma^{5/2}$}$
$\displaystyle\leq\frac{N}{\gamma^{3/2}\log^{2}\frac{N}{\log\frac{1}{\delta}}\log\frac{1}{\delta}}\quad\text{since
$\gamma\geq C$ for large enough constant $C$}$

To further justify the last line above, observe that
$\frac{\gamma^{3/4}}{\gamma^{5/2}}\leq\frac{1}{\gamma^{3/2}\cdot\gamma^{1/4}}$,
and that for large enough constant $C$, since $\gamma\geq C$, $\gamma^{1/4}$
can be made larger than any fixed constant. Also note that
$\log^{3/2}\left(2\left(\frac{N}{\log\frac{1}{\delta}}\right)^{4/3}\right)\leq\log^{2}\frac{N}{\log\frac{1}{\delta}}$
for large enough constant $C$ since
$\frac{N}{\log\frac{1}{\delta}}\geq\gamma\geq C$. So the inequality follows.
Next we bound $\frac{2t\sigma_{r}\sqrt{\alpha N}}{\sqrt{r}}$.

$\displaystyle\frac{2t\sigma_{r}\sqrt{\alpha N}}{\sqrt{r}}$
$\displaystyle=2\sqrt{\frac{N\sigma_{r}}{tr}}\quad\text{since
$\alpha=\frac{1}{t^{3}\sigma_{r}}$}$
$\displaystyle=2\sqrt{\frac{N\sigma_{r}}{r\gamma^{1/4}\sqrt{\frac{\log\frac{N}{\mathcal{I}_{r}r^{2}\log\frac{1}{\delta}}}{\mathcal{I}_{r}r^{2}}}}}\quad\text{since
$t=\gamma^{1/4}\sqrt{\frac{\log\frac{N}{\mathcal{I}_{r}r^{2}\log\frac{1}{\delta}}}{\mathcal{I}_{r}r^{2}}}$}$
$\displaystyle\leq
4\sqrt{\frac{N\sigma}{r\gamma^{1/4}\sqrt{\log\frac{N}{\log\frac{1}{\delta}}}}}\quad\text{since
$\mathcal{I}_{r}\leq\frac{1}{r^{2}}$ and $\sigma_{r}^{2}\leq 2\sigma^{2}$}$
$\displaystyle\leq
4\sqrt{\frac{N}{\gamma^{1/4}\sqrt{\log\frac{N}{\log\frac{1}{\delta}}}}\cdot\left(\frac{N}{\log\frac{1}{\delta}}\right)^{1/6}}\quad\text{by
\eqref{eq:sigma_over_r_density}}$ $\displaystyle\leq
4N\cdot\left(\frac{N}{\log\frac{1}{\delta}}\right)^{1/12}\quad\text{since
$\gamma\geq 1$, $\frac{N}{\log\frac{1}{\delta}}\geq 1$}$

So, we can now check the condition required to invoke Lemma D.3. We have

$\displaystyle\frac{12\log\left(\frac{2}{\delta}\left(\frac{2t\sigma_{r}\sqrt{\alpha
N}}{\sqrt{r}}+1\right)\right)+400\log\frac{1}{\alpha r}}{\alpha r}$
$\displaystyle\leq\left(12\log\left(\frac{2}{\delta}\left(4N\cdot\left(\frac{N}{\log\frac{1}{\delta}}\right)^{1/12}+1\right)\right)+400\log\frac{N}{\log\frac{1}{\delta}}\right)\left(\frac{N}{\gamma^{3/2}\log^{2}\frac{N}{\log\frac{1}{\delta}}\log\frac{1}{\delta}}\right)$
$\displaystyle\leq N\quad\text{since $\gamma\geq C$}$

So, by Lemma D.3, we have

$\displaystyle|\widehat{f}_{r}(x)-f_{r}(x)|\lesssim
f_{r}(x)\sqrt{\frac{1}{\alpha
rN}\log\left(\frac{2}{\delta}\left(\frac{2t\sigma_{r}\sqrt{\alpha
N}}{\sqrt{r}}+1\right)\right)\log\frac{2}{\alpha r}}$

We will show that the RHS above is bounded by
$O\left(\frac{f_{r}(x)}{\sqrt{\gamma}}\right)$. Since we showed that
$\frac{1}{\alpha
r}\leq\frac{N}{\gamma^{3/2}\log^{2}\frac{N}{\log\frac{1}{\delta}\log\frac{1}{\delta}}}$,
we have that

$\frac{1}{rN}\leq\frac{\alpha}{\gamma^{3/2}\log^{2}\frac{N}{\log\frac{1}{\delta}}\log\frac{1}{\delta}}$

So, plugging this into the RHS above, along with our bounds for
$\frac{2t\sigma_{r}\sqrt{\alpha N}}{\sqrt{r}}$ and $\frac{1}{\alpha r}$, we
have,

$\displaystyle|\widehat{f}_{r}(x)-f_{r}(x)|$
$\displaystyle\lesssim\frac{f_{r}(x)}{\sqrt{\gamma}}\cdot\sqrt{\frac{1}{\gamma^{1/2}\log^{2}\frac{N}{\log\frac{1}{\delta}}\log\frac{1}{\delta}}\log\left(\frac{2}{\delta}\left(4N\cdot\left(\frac{N}{\log\frac{1}{\delta}}\right)^{1/12}\right)+1\right)\log\left(\frac{N}{\gamma^{3/2}\log^{2}\frac{N}{\log\frac{1}{\delta}}\log\frac{1}{\delta}}\right)}$
$\displaystyle\lesssim\frac{f_{r}(x)}{\sqrt{\gamma}}$

So finally,

$\displaystyle\int_{-\infty}^{\infty}\left|\widehat{f}_{r}(x)-f_{r}(x)\right|\tilde{s}_{r}(x)^{2}\mathbbm{1}_{\\{|x-\mu|\leq
t\sigma_{r}\text{ and }f_{r}(x)\geq\alpha\\}}dx$
$\displaystyle\lesssim\frac{1}{\sqrt{\gamma}}\int_{-\infty}^{\infty}f_{r}(x)\tilde{s}_{r}(x)^{2}\mathbbm{1}_{\\{|x-\mu|\leq
t\sigma_{r}\text{ and }f_{r}(x)\geq\alpha\\}}dx$
$\displaystyle\leq\frac{1}{\sqrt{\gamma}}\operatorname*{\mathbb{E}}_{x\sim
f_{r}}[\tilde{s}_{r}(x)^{2}]$
$\displaystyle\lesssim\frac{\mathcal{I}_{r}}{\sqrt{\gamma}}\quad\text{since
$\operatorname*{\mathbb{E}}_{x\sim
f_{r}}[\tilde{s}_{r}(x)^{2}]\lesssim\mathcal{I}_{r}$ by assumption}$

See 4.6

######  Proof D.11.

We have

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim\widehat{f}_{r}}\left[\tilde{s}_{r}(x)^{2}\right]=\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[\tilde{s}_{r}(x)^{2}\right]+\int_{-\infty}^{\infty}\left(\widehat{f}_{r}(x)-f_{r}(x)\right)\tilde{s}_{r}(x)^{2}dx$

So, by our assumption,

$\displaystyle\left|\operatorname*{\mathbb{E}}_{x\sim\widehat{f}_{r}}[\tilde{s}_{r}(x)^{2}]-\mathcal{I}_{r}\right|\lesssim\frac{\mathcal{I}_{r}}{\sqrt{\gamma}}+\int_{-\infty}^{\infty}\left(\widehat{f}_{r}(x)-f_{r}(x)\right)\tilde{s}_{r}(x)^{2}dx$

It remains to bound the integral in the RHS above by
$O\left(\frac{\mathcal{I}_{r}}{\sqrt{\gamma}}\right)$. Let
$t=\gamma^{1/4}\sqrt{\frac{\log\frac{N}{\mathcal{I}_{r}r^{2}\log\frac{1}{\delta}}}{\mathcal{I}_{r}r^{2}}}$,
$\alpha=\frac{1}{t^{3}\sigma_{r}}$. We have

$\displaystyle\int_{-\infty}^{\infty}\left(\widehat{f}_{r}(x)-f_{r}(x)\right)\tilde{s}_{r}(x)^{2}dx$
$\displaystyle=\int_{-\infty}^{\infty}\left(\widehat{f}_{r}(x)-f_{r}(x)\right)s_{r}(x)^{2}\mathbbm{1}_{\\{|x-\mu|\leq
t\sigma_{r}\text{ and }f_{r}(x)\geq\alpha\\}}dx$
$\displaystyle\quad+\int_{-\infty}^{\infty}\left(\widehat{f}_{r}(x)-f_{r}(x)\right)\tilde{s}_{r}(x)^{2}\mathbbm{1}_{\\{|x-\mu|\leq
t\sigma_{r}\text{ and }f_{r}(x)<\alpha\\}}dx$
$\displaystyle\quad+\int_{-\infty}^{\infty}\left(\widehat{f}_{r}(x)-f_{r}(x)\right)\tilde{s}_{r}(x)^{2}\mathbbm{1}_{\\{|x-\mu|>t\sigma_{r}\\}}dx$

By Lemma D.9, the first term in the RHS above is bounded by
$\frac{\mathcal{I}_{r}}{\sqrt{\gamma}}$. To bound the other two terms, note
that

$\displaystyle\Pr_{x\sim f_{r}}\left[|x-\mu|\leq t\sigma_{r}\text{ and
}f_{r}(x)<\alpha\right]\leq\alpha t\sigma_{r}\lesssim\frac{1}{t^{2}}$

and by Chebyshev’s inequality,

$\displaystyle\Pr_{x\sim
f_{r}}\left[|x-\mu|>t\sigma_{r}\right]\leq\frac{1}{t^{2}}$

Also, for small constant $\beta>0$,

$\displaystyle\left(\frac{\gamma}{r^{4}\mathcal{I}_{r}^{2}}\right)^{1+\beta}$
$\displaystyle\leq\left(\frac{\gamma\sigma_{r}^{4}}{r^{4}}\right)^{1+\beta}\quad\text{since
$\mathcal{I}_{r}\geq\frac{1}{\sigma_{r}^{2}}$}$
$\displaystyle\leq\left(\frac{4\gamma\sigma^{4}}{r^{4}}\right)^{1+\beta}\quad\text{since
$\sigma_{r}^{2}=\sigma^{2}+r^{2}\leq 2\sigma^{2}$}$
$\displaystyle\leq\left(\gamma^{5/12}\frac{\sigma}{r}\right)^{6+\beta}\quad\text{since
$\gamma\geq C$ for large enough constant $C$, and $r\leq\sigma$}$
$\displaystyle\leq\frac{N}{\log\frac{1}{\delta}}$

So, the conditions of Lemma D.7 hold, and applying it to the second and third
term in the RHS above gives the claim.

##  Appendix E Local Estimation

In this section, we describe our local estimation procedure, which takes a
symmetrized and clipped KDE score function along with symmetrization point
$\mu_{1}=\mu+\varepsilon$, and produces a refined estimate $\widehat{\mu}$ of
the mean.

Algorithm 1 Local Estimation

#### Input Parameters:

  * •

$n$ samples $x_{1},\dots,x_{n}\sim f^{*}$, the symmetrized and clipped KDE
score function $\widehat{s}_{r}^{\text{sym}}$, symmetrization point $\mu_{1}$,
Fisher information estimate $\widehat{\mathcal{I}}_{r}$

  1. 1.

For each sample $x_{i}$, compute a perturbed sample
$x^{\prime}_{i}=x_{i}+\mathcal{N}(0,r^{2})$ where all the Gaussian noise are
drawn independently across all the samples.

  2. 2.

Compute
$\widehat{\varepsilon}=\frac{1}{\widehat{\mathcal{I}}_{r}n}\sum_{i=1}^{n}\widehat{s}_{r}^{\text{sym}}(x_{i}^{\prime})$.
Return $\widehat{\mu}=\mu_{1}-\widehat{\varepsilon}$.

See 4.8 See 4.9

######  Proof E.1.

Let $\mu_{1}=\mu+\varepsilon$. First, since by Property 4.8,

$\frac{1}{\widehat{\mathcal{I}}_{r}}|\widehat{s}_{r}^{\text{sym}}(x)|\leq\frac{2}{r\widehat{\mathcal{I}}_{r}}\sqrt{\log\frac{n}{\xi\log\frac{\xi}{\delta}}}\leq\left(1+O\left(\frac{1}{\sqrt{\gamma}}\right)\right)\frac{2}{r\mathcal{I}_{r}}\sqrt{\log\frac{n}{\xi\log\frac{\xi}{\delta}}}$

for all $x$, by Bernstein’s inequality, the estimate $\widehat{\varepsilon}$
satisfies that with probability $1-\delta$,

$\displaystyle\left|\widehat{\varepsilon}-\frac{1}{\widehat{\mathcal{I}}_{r}}\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[\widehat{s}_{r}^{\text{sym}}(x)\right]\right|\leq\frac{1}{\widehat{\mathcal{I}}_{r}}\sqrt{\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[\widehat{s}_{r}^{\text{sym}}(x)^{2}\right]}\sqrt{\frac{2\log\frac{2}{\delta}}{n}}+O\left(\frac{\sqrt{\log\frac{n}{\xi\log\frac{\xi}{\delta}}}}{r\mathcal{I}_{r}}\cdot\frac{\log\frac{2}{\delta}}{n}\right)$

Since
$|\widehat{\mathcal{I}}_{r}-\mathcal{I}_{r}|\lesssim\frac{\mathcal{I}_{r}}{\sqrt{\gamma}}$,
for $\gamma>C$ for sufficiently large constant $C$, we have

$\displaystyle\left|\frac{1}{\mathcal{I}_{r}}\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[\widehat{s}_{r}^{\text{sym}}(x)\right]-\frac{1}{\widehat{\mathcal{I}}_{r}}\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[\widehat{s}_{r}^{\text{sym}}(x)\right]\right|\lesssim\frac{1}{\mathcal{I}_{r}\sqrt{\gamma}}\left|\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[\widehat{s}_{r}^{\text{sym}}(x)\right]\right|\lesssim\frac{\varepsilon}{\sqrt{\gamma}}$

Combining this with the above and the fact that
$|\widehat{\mathcal{I}}_{r}-\mathcal{I}_{r}|\lesssim\frac{\mathcal{I}_{r}}{\sqrt{\gamma}}$
yields

$\displaystyle\left|\widehat{\varepsilon}-\frac{1}{\mathcal{I}_{r}}\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[\widehat{s}_{r}^{\text{sym}}(x)\right]\right|$
$\displaystyle\leq\left(1+O\left(\frac{1}{\sqrt{\gamma}}\right)\right)\frac{1}{\mathcal{I}_{r}}\sqrt{\operatorname*{\mathbb{E}}_{x\sim
f_{r}}\left[\widehat{s}_{r}^{\text{sym}}(x)^{2}\right]}\sqrt{\frac{2\log\frac{2}{\delta}}{n}}+O\left(\frac{\sqrt{\log\frac{n}{\xi\log\frac{\xi}{\delta}}}}{r\mathcal{I}_{r}}\cdot\frac{\log\frac{2}{\delta}}{n}\right)+O\left(\frac{\varepsilon}{\sqrt{\gamma}}\right)$

Then, combined with Property 4.8 and the triangle inequality, this implies
that with probability $1-\delta$,

$\displaystyle\left|\widehat{\varepsilon}-\varepsilon\right|\leq\left(1+O\left(\frac{1}{\sqrt{\gamma}}\right)\right)\sqrt{\frac{2\log\frac{2}{\delta}}{n\mathcal{I}_{r}}}+O\left(\frac{\sqrt{\log\frac{n}{\xi\log\frac{\xi}{\delta}}}}{r\mathcal{I}_{r}}\cdot\frac{\log\frac{2}{\delta}}{n}\right)+O\left(\frac{\varepsilon}{\sqrt{\gamma}}\right)$

So, since $\mu_{1}=\mu+\varepsilon$ and
$\widehat{\mu}=\mu+\widehat{\varepsilon}$, we have the claim.

##  Appendix F Global Estimation

In this section, we describe our global estimation procedure and show that it
provides a good estimate of the mean. It uses a small number of samples to
compute an initial estimate $\mu_{1}$ of $\mu$, and uses another small set of
samples to compute the symmetrized, clipped KDE score function
$\widehat{s}_{r}^{\text{sym}}$ symmetrized around $\mu_{1}$. It then uses our
local estimation procedure to produce the final estimate $\widehat{\mu}$.

Algorithm 2 Global Estimation

#### Input parameters:

  * •

Failure probability $\delta$, Samples $x_{1},\dots,x_{n}\sim f^{*}$, smoothing
parameter $r$, approximation parameter $\xi>0$.

  1. 1.

First, use the first $n/\xi$ samples to compute an initial estimate $\mu_{1}$
of the mean $\mu$ by using the Median-of-pairwise-means estimator in Lemma
4.11.

  2. 2.

Use the next $n/\xi$ samples to compute the kernel density estimate
$\widehat{f}_{r}$ of $f_{r}$ (as defined in (8)), along with the associated
symmeterized, clipped KDE score $\widehat{s}_{r}^{\text{sym}}$ (as defined in
(12)), clipped at $\frac{2}{r}\sqrt{\log\frac{n}{\xi\log\frac{\xi}{\delta}}}$
and symmetrized around the initial estimate $\mu_{1}$. Compute the Fisher
information estimate
$\widehat{\mathcal{I}}_{r}=\operatorname*{\mathbb{E}}_{x\sim\widehat{f}_{r}}\left[\widehat{s}_{r}^{\text{sym}}(x)^{2}\right]$.

  3. 3.