$\displaystyle\qquad\quad\sup_{\|w\|\geq\sqrt{k}}\frac{\ell^{H}_{{}_{\operatorname{{\rm
svm}},k}}(y,w)}{\int_{x\in\mathbb{R}^{d}}\ell^{H}_{{}_{\operatorname{{\rm
svm}},k}}(x,w){\rm d}P}\Biggl{\\}}$ $\displaystyle\leq$
$\displaystyle\max\left\\{(6+8kE_{1}^{2})\left(2+\frac{\|y\|_{H}}{E_{1}}\right),\
1+2kE_{1}^{2}+\sqrt{2}kE_{1}\|y\|_{H}\right\\}$ $\displaystyle=$
$\displaystyle(6+8kE_{1}^{2})\left(2+\frac{\|y\|_{H}}{E_{1}}\right)=s(y).$

Consequently, $s(y)$ is an upper sensitivity for
$(\mathbb{R}^{d},P,\mathbb{R}^{d},\ell_{\operatorname{{\rm svm}},k})$. Since
$\operatorname*{\mathbb{E}}_{y\sim
P}(\|y\|_{H})\leq\sqrt{\operatorname*{\mathbb{E}}_{y\sim
P}(\|y\|_{H}^{2})}\leq E_{1}$, for the total sensitivity, we have

$S=\int s(y){\rm d}P\leq(18+24kE_{1}^{2})=O(E_{1}^{2}k).$

With a similar proof, we can restate the following versions of Theorems 31 and
33 replacing $\operatorname{{\rm logistic}}$ by $\operatorname{{\rm svm}}$.

###### Theorem 40

Assume that $H$ is a reproducing kernel Hilbert space of real-valued functions
on $\mathcal{X}$ with kernel
$\boldsymbol{K}\colon\mathcal{X}\times\mathcal{X}\longrightarrow\mathbb{R}$
and $P$ is a probability measure over $\mathcal{X}$ such that
$\operatorname*{\mathbb{E}}\limits_{x\sim p}\|x\|_{H}^{2}\leq E_{1}$,

$s(x)=(6+8kE_{1}^{2})\left(2+\frac{\|y\|_{H}}{E_{1}}\right),$

and $S=O(E_{1}^{2}k)$. For
$m\geq\frac{2S}{\varepsilon^{2}}\left(8C^{2}+S\log\frac{2}{\delta}\right)$,
any $s$-sensitivity sample $x_{1},\ldots,x_{m}$ from $\mathcal{X}$ with
weights $u_{i}=\frac{S}{ms(x_{i})}$ provides an $\varepsilon$-coreset for
$(\mathcal{X},P,\mathcal{X},\ell^{H}_{\operatorname{{\rm svm}},k})$ )
respectively for
$(\mathcal{X},P,\mathcal{X},\bar{\ell}^{H}_{\operatorname{{\rm svm}},k})$)
with probability at least $1-\delta$, where
$C=(4E_{1}+2)\max\left(E_{1}k,1\right)+8E_{1}k+1$.

###### Theorem 41

Let $P$ be a probability measure over $\mathbb{R}^{d}$ such that
$\operatorname*{\mathbb{E}}\limits_{x\sim p}\|x\|_{2}^{2}\leq E_{1}^{2}$,
$s(x)=(6+8kE_{1}^{2})\left(2+\frac{\|y\|_{H}}{E_{1}}\right),$ and
$S=O\left(E_{1}^{2}k\right)$. For $m\geq
O\left(\frac{S}{\varepsilon^{2}}\left(d^{2}\log
S+\log\frac{1}{\delta}\right)\right)$, any $s$-sensitivity sample
$x_{1},\ldots,x_{m}$ from $\mathcal{X}$ with weights
$u_{i}=\frac{S}{ms(x_{i})}$ provides an $\varepsilon$-coreset for
$(\mathbb{R}^{d},P,\mathbb{R}^{d},\ell_{\operatorname{{\rm svm}},k})$ )
respectively for
$(\mathbb{R}^{d},P,\mathbb{R}^{d},\bar{\ell}^{H}_{\operatorname{{\rm
svm}},k})$) with probability at least $1-\delta$.

###  4.4 Coreset for ReLU Function

For $\text{ReLU}(t)=\max(0,t)$, we derive our results from those in previous
section using a simple trick. Assume that $H$ is a reproducing kernel Hilbert
space of real-valued functions on $\mathcal{X}$ with kernel
$\boldsymbol{K}\colon\mathcal{X}\times\mathcal{X}\longrightarrow\mathbb{R}$
and $P$ is a probability measure over $\mathcal{X}$ such that
$\operatorname*{\mathbb{E}}\limits_{x\sim p}\|x\|_{H}^{2}\leq E^{2}_{1}$ or
$P\left(\left\\{x\in\mathcal{X}\colon\|x\|_{H}\geq A\right\\}\right)=0$. It is
easy to verify that $\boldsymbol{K}^{\prime}(\cdot)=1+\boldsymbol{K}(\cdot)$
is also a reproducing kernel associated with $H^{\prime}$ with
$\operatorname*{\mathbb{E}}\limits_{x\sim
p}\|x\|_{H^{\prime}}^{2}\leq(1+E_{1})^{2}$ or
$P\left(\left\\{x\in\mathcal{X}\colon\|x\|_{H^{\prime}}\geq
1+A\right\\}\right)=0$. As $\operatorname{{\rm svm}}(1+t)=\max(0,-t)$, if we
plug $\boldsymbol{K}^{\prime}$ in the results given in the previous section,
we can replicate them for $\phi(t)=\max(0,-t)$ by replacing $E_{1}$ and $A$
with $(1+E_{1})$ and $(1+A)$. While $\phi$ is not precisely the ReLU function,
for the case that the kernel is the standard linear kernel in Euclidean space,

$\ell_{\phi,k}(x,w)=\max(0,-\langle
x,w\rangle)+\frac{1}{k}\|w\|_{2}^{2}=\max(0,\langle
x,-w\rangle)+\frac{1}{k}\|w\|_{2}^{2}=\ell_{\text{ReLU},k}(x,-w).$

This implies that if we have a coreset for
$(\mathbb{R}^{d},P,\mathbb{R}^{d},\ell_{\phi,k})$, it automatically serves as
a coreset for $(\mathbb{R}^{d},P,\mathbb{R}^{d},\ell_{\text{ReLU},k})$ as
well. It is noteworthy that this conclusion cannot be extended to general
kernels as $-\boldsymbol{K}(x,w)=\boldsymbol{K}(x,-w)$ is not generally true.

##  5 Proof of Theorem 3, Sensitivity Sampling Bound using VC Dimension

A _$P$ -range space_ is a tuple $(\mathcal{X},P,\mathcal{R})$ where
$(\mathcal{X},P)$ is a probability measure space and $\mathcal{R}$ is a subset
of $2^{\mathcal{X}}$ whose members are $P$-measurable.

###### Definition 42

Let $(\mathcal{X},P,\mathcal{R})$ be a $P$-range space. For an
$\varepsilon,\eta\in(0,1)$, the measure $\nu$ on $\mathcal{X}$ is called a
relative $(\varepsilon,\eta)$-approximation for $(\mathcal{X},P,\mathcal{R})$
if each $R\in\mathcal{R}$ is $\nu$-measurable and
$\sup_{R\in\mathcal{R}}\left|P(R)-\nu(R)\right|\leq\varepsilon\max(\eta,P(R)).$

A weaker version of the following lemma is implicit in the proof of Theorem 31
in (Feldman et al., 2020). Here, we provide what we believe is a simpler and
more direct proof; a key improvement is the use of Fubini’s theorem to
transform from integrating over $\mathcal{X}$ to over the range of the
function.

###### Lemma 43

Let $(\mathcal{X},P,\mathcal{F})$ be a positive definite tuple and $s(\cdot)$
be an upper sensitivity function for it with the total sensitivity $S$. If the
measure $\nu$ is a relative $(\varepsilon,\eta)$-approximation for
$(\mathcal{X},Q,\operatorname{\bf Ranges}(\mathcal{T}_{\mathcal{F}},\succ))$,
where ${\rm d}Q(x)=\frac{s(x)}{S}{\rm d}P(x)$, then for each
$f\in\mathcal{F}$,

$\displaystyle\Big{|}\int_{x\in\mathcal{X}}f(x){\rm d}P(x)-$
$\displaystyle\int_{x\in\mathcal{X}}\frac{Sf(x)}{s(x)}{\rm d}\nu(x)\Big{|}$
$\displaystyle\leq(\varepsilon+S\eta\varepsilon)\int_{x\in\mathcal{X}}f(x){\rm
d}P(x).$

Proof  As $\nu$ is a relative $(\varepsilon,\eta)$-approximation for
$(\mathcal{X},Q,\operatorname{\bf Ranges}(\mathcal{T}_{\mathcal{F}},\succ))$,
for all $f\in\mathcal{F},r\geq 0$, we have

$\displaystyle\Big{|}Q(\operatorname{\bf range}(T_{f},$
$\displaystyle\succ,r))-\nu(\operatorname{\bf range}(T_{f},\succ,r))\Big{|}$
(27) $\displaystyle\leq$
$\displaystyle\varepsilon\max\left(\eta,Q(\operatorname{\bf
range}(T_{f},\succ,r))\right).$

Consider an arbitrary $g=T_{f}\in\mathcal{T}_{\mathcal{F}}$ and $r\geq 0$.
Note that

$\displaystyle\int_{x\in\mathcal{X}}$ $\displaystyle\min\\{r,g(x)\\}{\rm
d}Q(x)$ (28)
$\displaystyle=\int_{x\in\mathcal{X}}\left(\int^{\infty}_{0}\mathbbm{1}_{{}_{0<t<\min\\{r,g(x)\\}}}{\rm
d}t\right){\rm d}Q(x)$
$\displaystyle=\int^{\infty}_{0}\left(\int_{x\in\mathcal{X}}\mathbbm{1}_{{}_{0<t<\min\\{r,g(x)\\}}}{\rm
d}Q(x)\right){\rm d}t\quad\quad\text{(*)}$
$\displaystyle=\int^{\infty}_{0}\left(\int_{x\in\mathcal{X}}\mathbbm{1}_{{}_{t<r}}\times\mathbbm{1}_{{}_{t<g(x)}}{\rm
d}Q(x)\right){\rm d}t$
$\displaystyle=\int^{\infty}_{0}\mathbbm{1}_{{}_{t<r}}\left(\int_{x\in\mathcal{X}}\mathbbm{1}_{{}_{t<g(x)}}{\rm
d}Q(x)\right){\rm d}t$ $\displaystyle=\int_{0}^{r}\left(\int_{\\{x\colon
g(x)>t\\}}{\rm d}Q(x)\right){\rm d}t$
$\displaystyle=\int_{0}^{r}Q(\operatorname{\bf range}(g,\succ,t)){\rm d}t,$

where $(*)$ is true due to Fubini’s Theorem. The same equality for $\nu$ also
holds. As $\nu$ is a relative $(\varepsilon,\eta)$-approximation for
$(\mathcal{X},\operatorname{\bf Ranges}(\mathcal{T}_{\mathcal{F}},Q,\succ))$,
we have

$\displaystyle\Big{|}\int_{x\in\mathcal{X}}$
$\displaystyle\min\\{r,g(x)\\}{\rm
d}Q(x)-\int_{x\in\mathcal{X}}\min\\{r,g(x)\\}{\rm d}\nu(x)\Big{|}$
$\displaystyle=\left|\int_{0}^{r}Q(\operatorname{\bf
range}(g,\succ,t))-\nu(\operatorname{\bf range}(g,\succ,t)){\rm d}t\right|$
$\displaystyle\leq\int_{0}^{r}\left|Q(\operatorname{\bf
range}(g,\succ,t))-\nu(\operatorname{\bf range}(g,\succ,t))\right|{\rm d}t$
$\displaystyle\leq\varepsilon\int_{0}^{r}\max\left(\eta,Q(\operatorname{\bf
range}(g,\succ,t))\right){\rm d}t.$

Via Inequality (1), for each $x\in\mathcal{X}$, we have
$\frac{f(x)}{\int_{z}f(z){\rm d}P(z)}\leq s(x)$ which is equivalent to
$g(x)=\frac{Sf(x)}{s(x)\int_{z}f(z){\rm d}P(z)}\leq S$. This implies
$\max_{x}g(x)\leq S$ is finite. So, by setting $r=\max g$,

$\displaystyle\Big{|}\int_{x\in\mathcal{X}}$ $\displaystyle g(x){\rm
d}Q(x)-\int_{x\in\mathcal{X}}g(x){\rm d}\nu(x)\Big{|}$ (29)
$\displaystyle\leq$ $\displaystyle\int_{0}^{\max
g}\varepsilon\max\left(\eta,Q(\operatorname{\bf range}(g,\succ,t))\right){\rm
d}t.$

Set $r_{g}=\sup\\{r\geq 0\colon Q(\operatorname{\bf
range}(g,\succ,r))\geq\eta\\}$. Note that for each $t\in[0,r_{g})$,
$Q(\operatorname{\bf range}(g,\succ,t))\geq\eta$ and for each $t>r_{g}$,
$Q(\operatorname{\bf range}(g,\succ,t))<\eta$. Taking these observations into
account, we obtain

$\displaystyle\int_{0}^{r_{g}}$
$\displaystyle\varepsilon\max\left(\eta,Q(\operatorname{\bf
range}(g,\succ,t))\right){\rm d}t$
$\displaystyle=\varepsilon\int_{0}^{r_{g}}Q(\operatorname{\bf
range}(g,\succ,t)){\rm d}t$ $\displaystyle\leq\varepsilon\int_{0}^{\max
g}Q(\operatorname{\bf range}(g,\succ,t)){\rm d}t$
$\displaystyle=\varepsilon\int_{x\in\mathcal{X}}g(x){\rm d}Q(x)=\varepsilon.$

Last equalities are true due to Equality (28) and
$\int_{x\in\mathcal{X}}g(x){\rm d}Q(x)=1$. By the fact that $\max_{x}g(x)\leq
S$,

$\displaystyle\int_{r_{g}}^{\max g}\max\left(\eta,Q(\operatorname{\bf
range}(g,\succ,t))\right)$ $\displaystyle{\rm d}t=\int^{\max
g}_{r_{g}}\eta{\rm d}t$ $\displaystyle\leq(\max g)\eta\leq S.$

Since $\int_{\mathcal{X}}g(x){\rm d}Q(x)=1$ and $\int_{\mathcal{X}}g(x){\rm
d}\nu=\frac{1}{\int_{\mathcal{X}}f(z){\rm
d}P(z)}\int_{\mathcal{X}}\frac{Sf(x)}{s(x)}{\rm d}\nu(x),$ we have

$\displaystyle\frac{1}{\int_{\mathcal{X}}f(z){\rm d}P(z)}$
$\displaystyle\times\Big{|}\int_{\mathcal{X}}f(x){\rm
d}P(x)-\int_{\mathcal{X}}\frac{Sf(x)}{s(x)}{\rm d}\nu(x)\Big{|}$
$\displaystyle=$ $\displaystyle\left|\int_{x\in\mathcal{X}}g(x){\rm
d}Q(x)-\int_{x\in\mathcal{X}}g(x){\rm d}\nu(x)\right|$
$\displaystyle\text{\footnotesize(Ineq.\leavevmode\nobreak\
\ref{ineq:maxf})}\leavevmode\nobreak\ \leq$ $\displaystyle\int_{0}^{\max
g}\varepsilon\max\left(\eta,Q(\operatorname{\bf range}(g,\succ,t))\right){\rm
d}t$ $\displaystyle=$
$\displaystyle\int_{0}^{r_{g}}\varepsilon\max\left(\eta,Q(\operatorname{\bf
range}(g,\succ,t))\right){\rm d}t$ $\displaystyle+\int_{r_{g}}^{\max
g}\varepsilon\max\left(\eta,Q(\operatorname{\bf range}(g,\succ,t))\right){\rm
d}t$ $\displaystyle=$ $\displaystyle\varepsilon+S\eta\varepsilon,$

completing the proof.

Following the idea of $(\nu,\alpha)$-sampling by Li et al. (2001), it was
proved by Har-Peled and Sharir (2011) that a sufficiently large sample
according to $P$ provides a relative $(\varepsilon,\eta)$-approximation for
$(\mathcal{X},P,\mathcal{R})$ with high probability, if the VC-dimension is
bounded.

######  Theorem 44 (Li et al., 2001; Har-Peled and Sharir, 2011)

Let $(\mathcal{X},P,\mathcal{R})$ be a $P$-range with VC-dimension $d$. There
is a universal constant $C$ such that, for any $\eta>0$, and
$\varepsilon,\delta\in(0,1)$, with probability at least $1-\delta$, any iid
sample $X=\\{x_{1},\ldots,x_{m}\\}$ according to $P$ with
$m\geq\frac{C}{\eta\varepsilon^{2}}\left(d\log\frac{1}{\eta}+\log\frac{1}{\delta}\right)$
satisfies

$\left|P(R)-\frac{|R\cap
X|}{m}\right|\leq\varepsilon\max\left(\eta,P(R)\right)\quad\quad\forall
R\in\mathcal{R}.$

######  Theorem 45 (Theorem 3, Restated)

Let $(\mathcal{X},P,\mathcal{F})$ be a positive definite tuple, and
$s\colon\mathcal{X}\longrightarrow(0,\infty)$ be an upper sensitivity function
for it with the total sensitivity $S=\int s(x){\rm d}P(x)$. There is a
universal constant $C$ such that, for any $0<\varepsilon,\delta<1$, if
$m\geq\frac{CS}{\varepsilon^{2}}\left(d\log S+\log\frac{1}{\delta}\right))$,
where $d={\rm VCdim}(\operatorname{\bf
Ranges}(\mathcal{T}_{\mathcal{F}},\succ))$, then, with probability at least
$1-\delta$, any $s$-sensitivity sample $x_{1}\ldots,x_{m}$ from $\mathcal{X}$
satisfies

$\displaystyle\Big{|}\int f(x){\rm
d}P(x)-\frac{1}{m}\sum_{i=1}^{m}\frac{Sf(x_{i})}{s(x_{i})}\Big{|}\leq\varepsilon\int
f(x){\rm d}P(x)\quad\quad\forall f\in\mathcal{F}.$

Proof  Since $(\mathcal{X},Q,\operatorname{\bf
Ranges}(\mathcal{T}_{\mathcal{F}},\succ))$ is a $Q$-range, for an
$\varepsilon\in(0,1)$ and $\eta=\frac{1}{S}$, Theorem 44 implies that there is
a universal constant $C$ such that, any iid sample
$X=\\{x_{1},\ldots,x_{m}\\}$ according to $Q$ with
$m\geq\frac{4CS}{\varepsilon^{2}}\left(d\log S+\log\frac{1}{\delta}\right)$
satisfies

$\left|Q(R)-\frac{|R\cap
X|}{m}\right|\leq\frac{\varepsilon}{2}\max\left(\frac{1}{S},Q(R)\right)\quad\quad\forall
R\in\mathcal{R},$

with probability at least $1-\delta$. This implies that the uniform
probability measure over $X$ serves as a relative
$\left(\frac{\varepsilon}{2},\frac{1}{S}\right)$-approximation for
$(\mathcal{X},Q,\operatorname{\bf Ranges}(\mathcal{T}_{\mathcal{F}},\succ))$.
The desired assertion is concluded by Lemma 43.

##  6 Related Works

In machine learning, a common scenario involves having a set of $n$ data
points and the goal of minimizing a data-driven objective loss function. At
times, for scalability reasons, it becomes necessary to choose a smaller
subset of $m\ll n$ points. The aim is to minimize the objective function on
these points, potentially using non-uniform weights for the selected points.
This approach aims to achieve a near-optimal solution for the entire data set.
Coresets are such (small) size $m$ subsets with guarantees on the associated
objective function. Coresets have found application in various problem
domains, such as clustering (Bundefineddoiu et al., 2002; Har-Peled and
Mazumdar, 2004; Frahling and Sohler, 2005, 2008; Feldman and Langberg, 2011;
Feldman and Schulman, 2012; Feldman et al., 2013; Braverman et al., 2019;
Huang and Vishnoi, 2020; Feldman et al., 2020), linear regression (Drineas et
al., 2006; Dasgupta et al., 2009; Clarkson et al., 2019), principal component
analysis (Cohen et al., 2015; Feldman et al., 2020), and more (Bachem et al.,
2017; Sener and Savarese, 2018; Munteanu et al., 2018; Sohler and Woodruff,
2018; Phillips and Tai, 2018b; Huang et al., 2018; Assadi et al., 2019; Mussay
et al., 2020).

Improving the prior result by Feldman and Langberg (2011) which suggests that
common sensitivity sampling requires $O(dS^{2})$ samples (for now ignoring
dependence on accuracy parameter $\varepsilon$), Braverman et al. (2021) and
Feldman et al. (2020) provide proofs that $O(dS\log S)$ is be sufficient.
Here, $S$ represents the total sensitivity, and $d$ is some VC-dimension
associated with the function space. The proof of these results benefits from a
connection between approximating a class of functions and approximating
associated range spaces. These associated range spaces – called _linked ranges
spaces_ by Joshi et al. (2011) who also defined these in this generality when
studying kernel density estimate coresets – are subsets of the domain defined
by sub-level sets from a function class. Joshi et al. (2011) showed that
$\varepsilon$-approximations for these linked range spaces induced
$\varepsilon$-approximations for functions spaces with bounded domains. It is
important to note that these results are subject to the assumption that the
input space is a finite set of $n$ samples (not a continuous probability
distribution). We eliminate this constraint in Theorem 3 with a different and
more straightforward proof outlined in Section 5. It is notable to highlight
that the coreset bounds derived from this theorem are all dependent on the
dimension, as VC-dimension for sub-level sets is intricately tied to dimension
in almost all reasonable cases. More importantly, we provide a counterpart of
this theorem (see Theorem 2) using Rademacher complexity in place of VC-
dimension, marking the first result of this kind. As a result, we are able to
present several coreset bounds independent of the dimension – the first such
results of this type (see Table 2). In the following, we focus more on the
related works pertaining to these findings.

Our work shares some connections with the research conducted by (Munteanu et
al., 2018; Mai et al., 2021; Tolochinksy et al., 2022; Curtin et al., 2020).
Munteanu et al. (2018) demonstrated the existence of datasets for which
coresets of sublinear size do not exist. They introduced a complexity measure
$\mu(X)$ for data points $X$, quantifying the difficulty associated with
compressing a dataset for logistic regression. They demonstrated the existence
of coresets with size $O^{*}(\frac{d^{3/2}\mu(X)\sqrt{|X|}}{\varepsilon^{2}})$
and $O^{*}(\frac{d^{3}\mu^{2}(X)}{\varepsilon^{4}})$ through a random sampling
procedure ($\mathcal{O}^{*}(\cdot)$ hides some logarithmic factors in terms of
the problem’s parameters). As a downside of their method, it is not clear how
to compute $\mu(X)$ and also they conjectured that computing the value of
$\mu(X)$ in general is hard. Moreover, their second bound is roughly quadratic
in terms of $\mu(X)$ and $\frac{1}{\varepsilon^{2}}$ when the data possesses a
small $\mu$-complexity. Following their work, Mai et al. (2021) improved these
bounds to $O^{*}(\frac{d\mu^{2}(X)}{\varepsilon^{2}})$ which is linear in
terms of $\frac{1}{\varepsilon^{2}}$. Their method relies on subsampling data
points with probabilities proportional to their $\ell_{1}$ Lewis weights. As
they utilize the complexity measure $\mu(X)$ in their context, which cannot be
directly interpreted in terms of our variables, presenting a meaningful
comparison between our findings and theirs becomes challenging. Nevertheless,
as an advantage, some of our bounds are independent of dimension, surpassing
their results in this particular aspect.

The most closely-related works to ours are (Tolochinksy et al., 2022) and
(Curtin et al., 2020). With an almost similar setting as ours, but these works
restrict to Euclidean space and with a bounded parameter space, Tolochinksy et
al. (2022) found the coresets of size $O^{*}\left(\frac{kd^{2}\log n\log
k}{\varepsilon^{2}}\right)$ for $\phi=\operatorname{{\rm
logistic}},\sigma,\operatorname{{\rm svm}}$. Enhancing some of these results,
Curtin et al. (2020) conducted an analysis of sampling-based coreset
constructions designed for regularized loss minimization problems (logistic
regression or SVM). Their context is slightly distinct from ours. To rephrase
their setting in the context of ours, we can express that in our setting, the
regularization term is $\frac{1}{k}$ whereas they roughly use
$\frac{1}{n^{1-\kappa}}$ for it (up to a constant). In the scenario where $k$
is proportional to $n^{1-\kappa}$ for a fixed $\kappa\in(0,1)$, they have
demonstrated that a uniform sample of size
$O^{*}\left(\frac{dn^{1-\kappa}}{\epsilon^{2}}\right)$ functions as a coreset
with high probability. Here, $n=|X|$ and $d$ represents a type of VC-dimension
linked to the function space (refer to the paper for the precise
definition).They have further established the tightness of uniform sampling,
accurate up to poly-logarithmic factors. A special case of our results not
only reproduces their results but also improves upon theirs for logistic
regression. It is still noteworthy that their bounds are dimension-dependent,
whereas we present some bounds independent of dimension. For a comprehensive
comparison, refer to Table 1.

A few other variants of coresets for classification exist for other objective
functions; we briefly mention a few. Munteanu et al. (2021) applies sketching
to create data compression for logistic regression. Their methods are data
oblivious and show improvements for sparse high-dimensional vectors. These
results are still polynomial in data parameter $\mu(X)$ and dimension $d$.
Mirzasoleiman et al. (2020) considers coresets for regularized classification
in the context of incremental gradient descent (IGD). They greedily select a
coreset to be used in IGD, and their results use that the
$\frac{1}{k}\|w\|^{2}$ regularizer makes loss function strongly convex as a
function of $k$. Coresets can also be found for the $0/1$ mis-classification
function of size $O(d/\varepsilon^{2})$ via classic VC-dimension arguments,
but as this cost function is non-convex over the model parameters $w$, the
best known algorithms (Matheny and Phillips, 2021) to solve for the
approximately optimal solution are still exponential in dimension
$O^{*}(1/\varepsilon^{d})$. Or if a dataset is known to be linearly separable,
then greedy coresets based on Frank-Wolfe can be found of size roughly
$O(1/\varepsilon)$ which approximately preserve that separation margin (Tsang
et al., 2005; Gärtner and Jaggi, 2009).

##  7 Conclusion and Discussion

This paper provides the first no dimensional sampling coresets for
classification; they provides relative error for standard loss functions on
linear classification with regularization, and an expectation bound on the
data norm. Some results apply to iid samples from a continuous distribution,
and hence imply sample complexity bounds. The key new ingredient is a
Radamacher complexity bound for sensitivity sample coresets, which we expect
will find further use.

We also show that these results extend to kernelized versions, and also
recover the best sampling bounds for KDE coresets.

While we do not provide new experimental evidence of the claims, our results
are consistent with simulations in many previous papers. For example
Tolochinksy et al. (2022) show non-uniform sensitivity sampling slightly out-
performing uniform samples; but this does not contradict our results using iid
samples since, for example, in those experiments doubling the iid sample size
improves upon the non-uniform sample results.

### Acknowledgements

Thanks to support from NSF CCF-2115677, CDS&E-1953350, IIS-1816149, and
IIS-2311954.

## References

  * Anthony and Bartlett (2009) Martin Anthony and Peter L. Bartlett.  _Neural Network Learning: Theoretical Foundations_.  Cambridge University Press, USA, 1st edition, 2009.  ISBN 052111862X.
  * Aronszajn (1950) N. Aronszajn.  Theory of reproducing kernels.  _Transactions of the American Mathematical Society_ , 68(3):337–404, 1950.  URL http://dx.doi.org/10.2307/1990404.
  * Assadi et al. (2019) Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein, Vahab Mirrokni, and Cliff Stein.  _Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs_ , pages 1616–1635.  2019\.  doi: 10.1137/1.9781611975482.98.  URL https://epubs.siam.org/doi/abs/10.1137/1.9781611975482.98.
  * Bachem et al. (2017) Olivier Bachem, Mario Lucic, and Andreas Krause.  Practical coreset constructions for machine learning.  _arXiv: Machine Learning_ , 2017.  URL https://api.semanticscholar.org/CorpusID:88517375.
  * Bobrowski et al. (2017) Omer Bobrowski, Sayan Mukherjee, and Jonathan E. Taylor.  Topological consistency via kernel estimation.  _Bernoulli_ , 23(1):288 – 328, 2017.  doi: 10.3150/15-BEJ744.  URL https://doi.org/10.3150/15-BEJ744.
  * Boser et al. (1992) Bernhard E. Boser, Isabelle M. Guyon, and Vladimir N. Vapnik.  A training algorithm for optimal margin classifiers.  In _Proceedings of the Fifth Annual Workshop on Computational Learning Theory_ , COLT ’92, page 144–152, New York, NY, USA, 1992. Association for Computing Machinery.  ISBN 089791497X.  doi: 10.1145/130385.130401.  URL https://doi.org/10.1145/130385.130401.
  * Braverman et al. (2019) Vladimir Braverman, Harry Lang, Enayat Ullah, and Samson Zhou.  Improved Algorithms for Time Decay Streams.  In Dimitris Achlioptas and László A. Végh, editors, _Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)_ , volume 145 of _Leibniz International Proceedings in Informatics (LIPIcs)_ , pages 27:1–27:17, Dagstuhl, Germany, 2019. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  ISBN 978-3-95977-125-2.  doi: 10.4230/LIPIcs.APPROX-RANDOM.2019.27.  URL https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.27.
  * Braverman et al. (2021) Vladimir Braverman, Dan Feldman, Harry Lang, Adiel Statman, and Samson Zhou.  Efficient coreset constructions via sensitivity sampling.  In Vineeth N. Balasubramanian and Ivor Tsang, editors, _Proceedings of The 13th Asian Conference on Machine Learning_ , volume 157 of _Proceedings of Machine Learning Research_ , pages 948–963. PMLR, 17–19 Nov 2021.  URL https://proceedings.mlr.press/v157/braverman21a.html.
  * Bundefineddoiu et al. (2002) Mihai Bundefineddoiu, Sariel Har-Peled, and Piotr Indyk.  Approximate clustering via core-sets.  In _Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing_ , STOC ’02, page 250–257, New York, NY, USA, 2002. Association for Computing Machinery.  ISBN 1581134959.  doi: 10.1145/509907.509947.  URL https://doi.org/10.1145/509907.509947.
  * Charikar et al. (2024) Moses Charikar, Michael Kapralov, and Erik Waingarten.  A quasi-monte carlo data structure for smooth kernel evaluations, 2024\.
  * Clarkson et al. (2019) Kenneth Clarkson, Ruosong Wang, and David Woodruff.  Dimensionality reduction for tukey regression.  In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, _Proceedings of the 36th International Conference on Machine Learning_ , volume 97 of _Proceedings of Machine Learning Research_ , pages 1262–1271. PMLR, 09–15 Jun 2019.  URL https://proceedings.mlr.press/v97/clarkson19a.html.
  * Cohen et al. (2015) Michael B. Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu.  Dimensionality reduction for k-means clustering and low rank approximation.  In _Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing_ , STOC ’15, page 163–172, New York, NY, USA, 2015. Association for Computing Machinery.  ISBN 9781450335362.  doi: 10.1145/2746539.2746569.  URL https://doi.org/10.1145/2746539.2746569.
  * Curtin et al. (2020) Ryan R. Curtin, Sungjin Im, Benjamin Moseley, Kirk Pruhs, and Alireza Samadian.  Unconditional coresets for regularized loss minimization.  In Silvia Chiappa and Roberto Calandra, editors, _Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics_ , volume 108 of _Proceedings of Machine Learning Research_ , pages 482–492. PMLR, 26–28 Aug 2020.  URL https://proceedings.mlr.press/v108/samadian20a.html.
  * Dasgupta et al. (2009) Anirban Dasgupta, Petros Drineas, Boulos Harb, Ravi Kumar, and Michael W. Mahoney.  Sampling algorithms and coresets for $\ell_{p}$ regression.  _SIAM Journal on Computing_ , 38(5):2060–2078, 2009.  doi: 10.1137/070696507.  URL https://doi.org/10.1137/070696507.
  * Drineas et al. (2006) Petros Drineas, Michael W. Mahoney, and S. Muthukrishnan.  Sampling algorithms for $\ell_{2}$ regression and applications.  In _Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm_ , SODA ’06, page 1127–1136, USA, 2006. Society for Industrial and Applied Mathematics.  ISBN 0898716055.
  * Feldman and Langberg (2011) Dan Feldman and Michael Langberg.  A unified framework for approximating and clustering data.  In _Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing_ , STOC ’11, page 569–578, New York, NY, USA, 2011. Association for Computing Machinery.  ISBN 9781450306911.  doi: 10.1145/1993636.1993712.  URL https://doi.org/10.1145/1993636.1993712.
  * Feldman and Schulman (2012) Dan Feldman and Leonard J. Schulman.  Data reduction for weighted and outlier-resistant clustering.  In _Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms_ , SODA ’12, page 1343–1354, USA, 2012. Society for Industrial and Applied Mathematics.
  * Feldman et al. (2013) Dan Feldman, Melanie Schmidt, and Christian Sohler.  Turning big data into tiny data: Constant-size coresets for k-means, pca and projective clustering.  In _Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms_ , SODA ’13, page 1434–1453, USA, 2013. Society for Industrial and Applied Mathematics.  ISBN 9781611972511.
  * Feldman et al. (2020) Dan Feldman, Melanie Schmidt, and Christian Sohler.  Turning big data into tiny data: Constant-size coresets for $k$-means, PCA, and projective clustering.  _SIAM Journal on Computing_ , 49(3):601–657, 2020\.  doi: 10.1137/18M1209854.  URL https://doi.org/10.1137/18M1209854.
  * Frahling and Sohler (2005) Gereon Frahling and Christian Sohler.  Coresets in dynamic geometric data streams.  In _Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing_ , STOC ’05, page 209–217, New York, NY, USA, 2005. Association for Computing Machinery.  ISBN 1581139608.  doi: 10.1145/1060590.1060622.  URL https://doi.org/10.1145/1060590.1060622.
  * Frahling and Sohler (2008) Gereon Frahling and Christian Sohler.  A fast k-means implementation using coresets.  _International Journal of Computational Geometry & Applications_, 18(06):605–625, 2008.  doi: 10.1142/S0218195908002787.  URL https://doi.org/10.1142/S0218195908002787.
  * Fubini (1907) Guido Fubini.  Sugli integrali multipli.  _Reale Accademia dei Lincei, Rome_ , 16(1):608–614, 1907.
  * Gärtner and Jaggi (2009) Bernd Gärtner and Martin Jaggi.  Coresets for polytope distance.  In _Proceedings of the twenty-fifth annual symposium on Computational geometry_ , pages 33–42, 2009.
  * Gretton et al. (2012) Arthur Gretton, Karsten M. Borgwardt, Malte J. Rasch, Bernhard Schölkopf, and Alexander Smola.  A kernel two-sample test.  _Journal of Machine Learning Research_ , 13(25):723–773, 2012.  URL http://jmlr.org/papers/v13/gretton12a.html.
  * Har-Peled and Mazumdar (2004) Sariel Har-Peled and Soham Mazumdar.  On coresets for k-means and k-median clustering.  In _Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing_ , STOC ’04, page 291–300, New York, NY, USA, 2004. Association for Computing Machinery.  ISBN 1581138520.  doi: 10.1145/1007352.1007400.  URL https://doi.org/10.1145/1007352.1007400.
  * Har-Peled and Sharir (2011) Sariel Har-Peled and Micha Sharir.  Relative ($p,\epsilon$)-approximations in geometry.  _Discrete & Computational Geometry_, 45(3):462–496, 2011.  doi: 10.1007/s00454-010-9248-1.  URL https://doi.org/10.1007/s00454-010-9248-1.
  * Huang and Vishnoi (2020) Lingxiao Huang and Nisheeth K. Vishnoi.  Coresets for clustering in euclidean spaces: Importance sampling is nearly optimal.  In _Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing_ , STOC 2020, page 1416–1429, New York, NY, USA, 2020. Association for Computing Machinery.  ISBN 9781450369794.  doi: 10.1145/3357713.3384296.  URL https://doi.org/10.1145/3357713.3384296.
  * Huang et al. (2018) Lingxiao Huang, Shaofeng H.-C. Jiang, Jian Li, and Xuan Wu.  Epsilon-coresets for clustering (with outliers) in doubling metrics.  In _2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)_ , pages 814–825, 2018.  doi: 10.1109/FOCS.2018.00082.
  * Joshi et al. (2011) Sarang Joshi, Raj Varma Kommaraji, Jeff M. Phillips, and Suresh Venkatasubramanian.  Comparing distributions and shapes using the kernel distance.  In _Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry_ , SoCG ’11, page 47–56, New York, NY, USA, 2011. Association for Computing Machinery.  ISBN 9781450306829.  doi: 10.1145/1998196.1998204.  URL https://doi.org/10.1145/1998196.1998204.
  * Karnin and Liberty (2019) Zohar Karnin and Edo Liberty.  Discrepancy, coresets, and sketches in machine learning.  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 1975–1993. PMLR, 25–28 Jun 2019.  URL https://proceedings.mlr.press/v99/karnin19a.html.
  * Lacoste-Julien et al. (2015) Simon Lacoste-Julien, Fredrik Lindsten, and Francis Bach.  Sequential Kernel Herding: Frank-Wolfe Optimization for Particle Filtering.  In _18th International Conference on Artificial Intelligence and Statistics (AISTATS)_ , volume 38 of _JMLR Workshop and Conference Proceedings_ , San Diego, United States, May 2015.  URL https://hal.science/hal-01099197.
  * Ledoux and Talagrand (1991) Michel. Ledoux and Michel. Talagrand.  _Probability in Banach Spaces [electronic resource] : Isoperimetry and Processes / by Michel Ledoux, Michel Talagrand._ Classics in Mathematics. Springer Berlin Heidelberg, Berlin, Heidelberg, 1st ed. 1991. edition, 1991.  ISBN 3-642-20212-8.
  * Li et al. (2001) Yi Li, Philip M. Long, and Aravind Srinivasan.  Improved bounds on the sample complexity of learning.  _Journal of Computer and System Sciences_ , 62(3):516–527, 2001.  ISSN 0022-0000.  doi: https://doi.org/10.1006/jcss.2000.1741.  URL https://www.sciencedirect.com/science/article/pii/S0022000000917410.
  * Lopez-Paz et al. (2015) David Lopez-Paz, Krikamol Muandet, Bernhard Schölkopf, and Iliya Tolstikhin.  Towards a learning theory of cause-effect inference.  In Francis Bach and David Blei, editors, _Proceedings of the 32nd International Conference on Machine Learning_ , volume 37 of _Proceedings of Machine Learning Research_ , pages 1452–1461, Lille, France, 07–09 Jul 2015. PMLR.  URL https://proceedings.mlr.press/v37/lopez-paz15.html.
  * Mai et al. (2021) Tung Mai, Cameron N Musco, and Anup Rao.  Coresets for classification – simplified and strengthened.  In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, _Advances in Neural Information Processing Systems_ , 2021.  URL https://openreview.net/forum?id=qz0MLeaTP1C.
  * Matheny and Phillips (2021) Michael Matheny and Jeff M Phillips.  Approximate maximum halfspace discrepancy.  In _32nd International Symposium on Algorithms and Computation (ISAAC 2021)_. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021.
  * Matousek (2002) Jiri Matousek.  _Lectures on Discrete Geometry_.  Springer-Verlag, Berlin, Heidelberg, 2002.  ISBN 0387953744.
  * McDiarmid (1989) Colin McDiarmid.  _On the method of bounded differences_ , page 148–188.  London Mathematical Society Lecture Note Series. Cambridge University Press, 1989.  doi: 10.1017/CBO9781107359949.008.
  * Mercer (1909) J. Mercer.  Functions of positive and negative type, and their connection with the theory of integral equations.  _Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character_ , 209:415–446, 1909.  ISSN 02643952.  URL http://www.jstor.org/stable/91043.
  * Mirzasoleiman et al. (2020) Baharan Mirzasoleiman, Jeff Bilmes, and Jure Leskovec.  Coresets for data-efficient training of machine learning models.  In _International Conference on Machine Learning_ , pages 6950–6960. PMLR, 2020.
  * Munteanu et al. (2018) Alexander Munteanu, Chris Schwiegelshohn, Christian Sohler, and David P. Woodruff.  On coresets for logistic regression.  In _Proceedings of the 32nd International Conference on Neural Information Processing Systems_ , NIPS’18, page 6562–6571, Red Hook, NY, USA, 2018. Curran Associates Inc.
  * Munteanu et al. (2021) Alexander Munteanu, Simon Omlor, and David Woodruff.  Oblivious sketching for logistic regression.  In Marina Meila and Tong Zhang, editors, _Proceedings of the 38th International Conference on Machine Learning_ , volume 139 of _Proceedings of Machine Learning Research_ , pages 7861–7871. PMLR, 18–24 Jul 2021.  URL https://proceedings.mlr.press/v139/munteanu21a.html.
  * Mussay et al. (2020) Ben Mussay, Margarita Osadchy, Vladimir Braverman, Samson Zhou, and Dan Feldman.  Data-independent neural pruning via coresets.  In _International Conference on Learning Representations_ , 2020.  URL https://openreview.net/forum?id=H1gmHaEKwB.
  * Phillips (2016) Jeff M. Phillips.  Coresets and sketches.  In _Handbook of Discrete and Computational Geometry_ , chapter 49. CRC Press, 2016.
  * Phillips and Tai (2018a) Jeff M. Phillips and Wai Ming Tai.  _Improved Coresets for Kernel Density Estimates_ , pages 2718–2727.  2018a.  doi: 10.1137/1.9781611975031.173.  URL https://epubs.siam.org/doi/abs/10.1137/1.9781611975031.173.
  * Phillips and Tai (2018b) Jeff M. Phillips and Wai Ming Tai.  Improved coresets for kernel density estimates.  In _Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms_ , SODA ’18, page 2718–2727, USA, 2018b. Society for Industrial and Applied Mathematics.  ISBN 9781611975031.
  * Phillips and Tai (2020) Jeff M. Phillips and Wai Ming Tai.  Near-optimal coresets of kernel density estimates.  _Discrete & Computational Geometry_, 63(4):867–887, 2020.  doi: 10.1007/s00454-019-00134-6.  URL https://doi.org/10.1007/s00454-019-00134-6.
  * Phillips et al. (2015) Jeff M. Phillips, Bei Wang, and Yan Zheng.  Geometric Inference on Kernel Density Estimates.  In Lars Arge and János Pach, editors, _31st International Symposium on Computational Geometry (SoCG 2015)_ , volume 34 of _Leibniz International Proceedings in Informatics (LIPIcs)_ , pages 857–871, Dagstuhl, Germany, 2015. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  ISBN 978-3-939897-83-5.  doi: 10.4230/LIPIcs.SOCG.2015.857.  URL https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.857.
  * Rinaldo and Wasserman (2010) Alessandro Rinaldo and Larry Wasserman.  Generalized density clustering.  _The Annals of Statistics_ , 38(5):2678 – 2722, 2010.  doi: 10.1214/10-AOS797.  URL https://doi.org/10.1214/10-AOS797.
  * Schölkopf and Smola (2018) Bernhard Schölkopf and Alexander J. Smola.  _Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond_.  The MIT Press, 06 2018.  ISBN 9780262256933.  doi: 10.7551/mitpress/4175.001.0001.  URL https://doi.org/10.7551/mitpress/4175.001.0001.
  * Scott (2015) D. W. Scott.  _Multivariate Density Estimation: Theory, Practice, and Visualization_.  2015\.
  * Sener and Savarese (2018) Ozan Sener and Silvio Savarese.  Active learning for convolutional neural networks: A core-set approach.  In _International Conference on Learning Representations_ , 2018.  URL https://openreview.net/forum?id=H1aIuk-RW.
  * Shalev-Shwartz and Ben-David (2014) Shai Shalev-Shwartz and Shai Ben-David.  _Understanding Machine Learning: From Theory to Algorithms_.  Cambridge University Press, USA, 2014.  ISBN 1107057132.
  * Silverman (1986) B. W. Silverman.  _Density Estimation for Statistics and Data Analysis_.  Chapman & Hall, London, 1986.
  * Sohler and Woodruff (2018) Christian Sohler and David P. Woodruff.  Strong coresets for k-median and subspace approximation: Goodbye dimension.  In _2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)_ , pages 802–813, 2018.  doi: 10.1109/FOCS.2018.00081.
  * Steinwart and Christmann (2008) Ingo Steinwart and Andreas Christmann.  _Support Vector Machines_.  Springer Publishing Company, Incorporated, 1st edition, 2008.  ISBN 0387772413.
  * Tai (2022) Wai Ming Tai.  Optimal Coreset for Gaussian Kernel Density Estimation.  In Xavier Goaoc and Michael Kerber, editors, _38th International Symposium on Computational Geometry (SoCG 2022)_ , volume 224 of _Leibniz International Proceedings in Informatics (LIPIcs)_ , pages 63:1–63:15, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  ISBN 978-3-95977-227-3.  doi: 10.4230/LIPIcs.SoCG.2022.63.  URL https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.63.
  * Taylor (2018) C. C. Taylor.  Nonparametric Density Estimation: The L1 View.  _Royal Statistical Society. Journal. Series A: General_ , 148(4):392–393, 12 2018.  ISSN 0035-9238.  doi: 10.2307/2981908.  URL https://doi.org/10.2307/2981908.
  * Tolochinksy et al. (2022) Elad Tolochinksy, Ibrahim Jubran, and Dan Feldman.  Generic coreset for scalable learning of monotonic kernels: Logistic regression, sigmoid and more.  In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, _Proceedings of the 39th International Conference on Machine Learning_ , volume 162 of _Proceedings of Machine Learning Research_ , pages 21520–21547. PMLR, 17–23 Jul 2022.
  * Tsang et al. (2005) Ivor W Tsang, James T Kwok, Pak-Ming Cheung, and Nello Cristianini.  Core vector machines: Fast svm training on very large data sets.  _Journal of Machine Learning Research_ , 6(4), 2005.
  * Zheng and Phillips (2015) Yan Zheng and Jeff M. Phillips.  $l_{\infty}$ error and bandwidth selection for kernel density estimates of large data.  In _Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , KDD ’15, pages 1533–1542, New York, NY, USA, 2015. Association for Computing Machinery.  ISBN 9781450336642.  doi: 10.1145/2783258.2783357.  URL https://doi.org/10.1145/2783258.2783357.


$m^{2}_{\mathrm{miss}}$ regions can be explored in the PNN data sample without
violating the blind analysis principle. The distribution of
$m^{2}_{\mathrm{miss}}$ for the selected data and simulated events is shown in
Figure 18: simulated upstream events explain the shape of the data. The sample
is dominated by $K^{+}\to\pi^{+}\pi^{+}\pi^{-}$ and $K^{+}\to\pi^{+}\pi^{0}$
decays occurring downstream of the first GTK station (GTK1).

The $X,Y$ coordinates of the pions selected in the data sample, obtained by
extrapolating their tracks to the $(X,Y)$ plane of the final collimator, are
shown in Figure 19 (left). In most cases, the pion passes through the beam
hole in the final collimator. The shape of the distribution outside of the
hole is determined by the material in the beam line: most of the pions outside
the hole are contained in the aperture of the last dipole magnet of the beam
line. Pions from upstream in-time events, originating from GTK3, have an $X,Y$
distribution at the final collimator which overlaps with the $X,Y$
distribution of pions from accidental upstream events. The box cut used in the
PNN selection, $|X|<100$ mm, $|Y|<500$ mm (section 5.6) is defined to exclude
the whole aperture of the magnet.

The time structure of the selected upstream events is shown in Figure 19
(right). Accidental coincidence between KTAG and GTK signals is necessary to
reconstruct a $K^{+}$ candidate in events with a $K^{+}$ decaying or
interacting upstream of GTK3. On the other hand, the $\pi^{+}$ in these events
produces a RICH signal in time with the KTAG signal of the parent $K^{+}$.
Therefore accidental upstream events of types a) and c) populate the
horizontal band in the timing plot. Accidental upstream events of types b) and
d) require a pileup $K^{+}$ in the GTK. In this case one of the two KTAG
candidates and the GTK track are in time, while the $\pi^{+}$ signal in the
RICH accidentally coincides with the same KTAG candidate. As a consequence,
accidental upstream events of types b) and d) form the vertical band in the
timing plot. In-time upstream events populate the central region of the plot.
The distribution of data events in the central region is consistent with that
formed by the overlap of the horizontal and vertical bands, and indicates that
in-time upstream events account for less than 10% of the sample, which is in
agreement with simulations.

Figure 20: Sketch of an accidental upstream event of type a) in the horizontal
plane (not to scale). The GTK stations GTK1, GTK2 and GTK3 are displayed
together with the final collimator. The reconstructed $\pi^{+}$ fails the box
cut because of the large-angle scattering at STRAW1.

The PNN selection criteria mostly effective against accidental upstream
background are:

  * •

the $K/\pi$ association: a coincidence between the two independent particles
can only occur accidentally;

  * •

the $Z_{\rm vertex}$ conditions defining the FV: a $K^{+}\to\pi^{+}$ decay
vertex can only be reconstructed in the FV accidentally;

  * •

the box cut: the $\pi^{+}$ satisfies this condition only if mis-reconstructed
or suffering large-angle scattering at STRAW1;

  * •

the rejection of events with extra hits in at least two GTK stations: the beam
particle producing the $\pi^{+}$ disappears along the beam line in the GTK
region; simulations indicate that $\pi^{+}$ produced upstream of GTK1 cannot
reach the FV; mostly $K^{+}$ travelling outside the GTK acceptance can pass
this condition, as the probability to lose a hit in a GTK station is
negligible.

The first three criteria also suppress in-time upstream events along with the
CHANTI veto conditions.

An accidental upstream event of type a) contributing to the background is
sketched in Figure 20. The parent kaon decays ($K^{+}\to\pi^{+}\pi^{0}$)
downstream of GTK2. The photons from $\pi^{0}\to\gamma\gamma$ decay are
absorbed by the final collimator, while the $\pi^{+}$ propagates in the
magnetic field through the collimator aperture. Finally, the $\pi^{+}$
direction is modified by large-angle scattering at STRAW1.

Figure 21: Left: CDA distribution of upstream events selected as described in
the text. The distribution is compared with a model obtained from simulations.
The CDA distribution of data events coming from $K^{+}$ decays in the FV is
also shown. Right: probability for an upstream event to satisfy the $K/\pi$
matching conditions as a function of $\Delta$T(GTK–KTAG) obtained using the
CDA model shown in the left plot.

####  7.2.2 Upstream background evaluation

The evaluation of the upstream background in the PNN sample does not rely on
Monte Carlo simulation, but follows a data-driven approach. A sample of PNN
data enriched with upstream events, called the “upstream sample” below, is
selected using modified PNN criteria: ${\rm CDA}>4$ mm is required instead of
the $K/\pi$ matching conditions. The number of events from the PNN sample
passing this selection is $N_{\rm data}=16$. The background from $K^{+}$
decays in the FV in this sample is estimated to be 0.2 events by analysing
background regions of $m^{2}_{\mathrm{miss}}$ with the methods described in
sections 7.1.1 and 7.1.2.

The upstream background is evaluated considering the probability $P_{\rm
mistag}$ that an upstream event satisfies the $K/\pi$ matching criteria. This
probability depends only on the shape of the CDA distribution and the time
difference $\Delta$T(GTK–KTAG) for the events in the horizontal band of Figure
19 (right), and $\Delta$T(KTAG–RICH) for the events in the vertical band. The
CDA distribution model is established from simulations of accidental upstream
events. This model is validated using a data sample selected similarly to the
upstream sample with the following modifications: GTK and CHANTI veto
conditions are removed, the condition CDA$>4$ mm is removed, and a timing
condition $0.6~{}{\rm ns}<|$T(KTAG–GTK)$|<3~{}{\rm ns}$ is used. Data and
simulations agree within the statistical uncertainties, as shown in Figure 21
(left). The probability $P_{\rm mistag}$ evaluated with simulations in bins of
$\Delta T$ is shown in Figure 21 (right). The number of upstream background
events is estimated in each of the two bands shown in Figure 19 (right) as

$N_{\rm upstream}=f_{\rm scale}\cdot\sum_{i=1}^{12}N_{data}^{i}P_{\rm
mistag}^{i}~{}~{},$ (16)

where the sum runs over twelve 100 ps wide $\Delta$T bins covering the
$(-0.6,0.6)$ ns range; $N_{\rm data}^{i}$ is the number of events found in the
upstream sample in bin $i$, $P_{\rm mistag}^{i}$ is the corresponding mis-
tagging probability shown in Figure 21 (right), and $f_{\rm scale}=1.06$
accounts for upstream events with ${\rm CDA}\leq 4$ mm not included in the
$N_{\rm data}$ definition. The last factor is obtained from a study of the
T(GTK–KTAG) sidebands, as data and simulations show that the CDA is
independent of this quantity.

The procedure described above is validated using seven different data samples
selected modifying the PNN criteria as follows:

  1. 1.

$|X_{\rm col}|<100$ mm, $|Y_{\rm col}|<140$ mm for the pion position in the
final collimator plane, replacing the box cut;

  2. 2.

$|X_{\rm col}|<100$ mm, $|Y_{\rm col}|\geq 140$ mm, replacing the box cut;

  3. 3.

$m^{2}_{\mathrm{miss}}<-0.05~{}{\rm GeV}^{2}/c^{4}$, replacing the signal
region mass definition;

  4. 4.

as 1), without GTK and CHANTI veto conditions;

  5. 5.

as 2), without GTK and CHANTI veto conditions;

  6. 6.

as 3), without GTK and CHANTI veto conditions;

  7. 7.

GTK and CHANTI veto conditions inverted.

Simulations show that the contributions of the various types of upstream
background differ among the samples. The numbers of expected and observed
background events in each sample are presented in Figure 22: they agree within
one standard deviation in each sample.

Figure 22: Number of expected and observed events in the seven different upstream background validation samples. Table 10: Expected numbers of SM $K^{+}\rightarrow\pi^{+}\nu\bar{\nu}$ decays and of background events in the signal regions. Process | Events expected
---|---
$K^{+}\rightarrow\pi^{+}\nu\bar{\nu}$ (SM) | $2.16\pm 0.13_{\rm syst}\pm 0.26_{\rm ext}$
$K^{+}\rightarrow\pi^{+}\pi^{0}(\gamma)$ | $0.29\pm 0.03_{\rm stat}\pm 0.03_{\rm syst}$
$K^{+}\rightarrow\mu^{+}\nu(\gamma)$ | $0.15\pm 0.02_{\rm stat}\pm 0.04_{\rm syst}$
$K^{+}\rightarrow\pi^{+}\pi^{-}e^{+}\nu$ | $0.12\pm 0.05_{\rm stat}\pm 0.06_{\rm syst}$
$K^{+}\rightarrow\pi^{+}\pi^{+}\pi^{-}$ | $0.008\pm 0.008_{\rm syst}$
$K^{+}\rightarrow\pi^{+}\gamma\gamma$ | $0.005\pm 0.005_{\rm syst}$
$K^{+}\rightarrow\pi^{0}\ell^{+}\nu~{}(\ell=\mu,e)$ | $<0.001$
Upstream background | $0.89\pm 0.24_{\rm stat}\pm 0.20_{\rm syst}$
Total background | $1.46\pm 0.25_{\rm stat}\pm 0.21_{\rm syst}$

The number of expected upstream background events is found to be

$N_{\rm upstream}=0.89\pm 0.24_{\rm stat}\pm 0.20_{\rm syst}.$ (17)

The statistical uncertainty stems from $N_{\rm data}$. A systematic
uncertainty of 12% is due to the modelling of the CDA distribution, and is
derived from the comparison between data and simulations. An additional
systematic uncertainty of 20% is assigned as half of the difference between
the expected and observed number of events in sample 6 (with statistics
similar to the expected signal). This uncertainty accounts for the accuracy of
the assumption that all the categories of upstream events have the same CDA
distribution.

###  7.3 Summary

The expected backgrounds in signal region are summarized in Table 10.

As an additional check, the expected and observed numbers of events in the PNN
sample are compared in a control region defined by the same
$m^{2}_{\mathrm{miss}}$ range as the signal regions 1 and 2 but in the 35–40
GeV$/c$ $\pi^{+}$ momentum range. The expected number of background events
here is between 0.4 and 0.8 at 90% CL, almost equally shared between $K^{+}$
decays in the FV and upstream events. The corresponding expected number of SM
$K^{+}\rightarrow\pi^{+}\nu\bar{\nu}$ events is $0.13\pm 0.02$. One event is
observed with a $\pi^{+}$ momentum of 38 GeV/c and
$m^{2}_{\mathrm{miss}}\simeq 0.03$ GeV${}^{2}/c^{4}$, in agreement with the
expectation.

##  8 Results

After unmasking the signal regions, two candidate events are found, as shown
in Figure 23.

Figure 23:  Reconstructed $m^{2}_{\mathrm{miss}}$ as a function of $\pi^{+}$
momentum for PNN events (full symbols) satisfying the PNN selection, except
the $m^{2}_{\mathrm{miss}}$ and $\pi^{+}$ momentum criteria. The grey area
corresponds to the expected distribution of SM
$K^{+}\rightarrow\pi^{+}\nu\bar{\nu}$ MC events (arbitrarily normalized). Red
contours define the signal regions. The events observed in the signal regions
are shown together with the events found in the background and control
regions.

Figure 24: Reconstructed $m^{2}_{\mathrm{miss}}$ distribution of data events
with $\pi^{+}$ momentum between 15 and 35 GeV/$c$, passing the PNN selection
(full symbols). The expected background and SM signal events contributions are
superimposed as stacked histograms. The $m^{2}_{\mathrm{miss}}$ distributions
of the $K^{+}\rightarrow\pi^{+}\pi^{0}$, $K^{+}\rightarrow\mu^{+}\nu$ and
$K^{+}\rightarrow\pi^{+}\pi^{+}\pi^{-}$ decays and of the upstream events are
extracted from data. The other contributions are obtained from simulations.

The second and third columns of Table 11 summarize the characteristics of
these events.

Table 11: Observed events in the signal regions after PNN selection. Events 1 and 2 come from the analysis of the 2017 data presented here. Event 3 comes from the analysis of the 2016 data. | Event 1 | Event 2 | Event 3
---|---|---|---
Year | 2017 | 2017 | 2016
$m^{2}_{\mathrm{miss}}$ | $0.038\,\text{GeV}^{2}/c^{4}$ | $0.064\,\text{GeV}^{2}/c^{4}$ | $0.031\,\text{GeV}^{2}/c^{4}$
$\pi^{+}$ momentum | $26.5\,\text{GeV}/c$ | $22.4\,\text{GeV}/c$ | $15.4\,\text{GeV}/c$
$Z_{vertex}$ |  $140$ m |  $159$ m |  $146$ m
$\Delta$T(KTAG - GTK) |  $-0.171$ ns |  $0.028$ ns |  $0.006$ ns
$\Delta$T(RICH - KTAG) |  $-0.082$ ns |  $0.209$ ns |  $0.040$ ns
$(X,Y)$ at final collimator |  $(228.4,104.1)$ mm |  $(189.4,-271.7)$ mm |  $(-372.6,29.8)$ mm

Figure 24 shows the $m^{2}_{\mathrm{miss}}$ distribution of the events with
momentum between 15 and 35 GeV/$c$ passing the PNN selection, compared with
that expected from SM $K^{+}\rightarrow\pi^{+}\nu\bar{\nu}$ decays and from
the various sources of background. In this plot the $m^{2}_{\mathrm{miss}}$
distribution of the $K^{+}\rightarrow\pi^{+}\pi^{0}$,
$K^{+}\rightarrow\mu^{+}\nu$ and $K^{+}\rightarrow\pi^{+}\pi^{+}\pi^{-}$
decays come from the minimum-bias samples, and normalized to the number of
events in the corresponding background regions (sections 7.1.1, 7.1.2 and
7.1.3). The distribution of the $m^{2}_{\mathrm{miss}}$ of the upstream
background is extracted from an upstream-event-enriched data sample and is
normalized to the number of upstream background events expected in the signal
regions. The distributions of the other background sources are modelled using
MC simulations and normalized to the expected number of events in the signal
regions.

The two candidate $K^{+}\rightarrow\pi^{+}\nu\bar{\nu}$ events of this
analysis complement the one found by NA62 in the same signal region from the
analysis of the 2016 data [20]. The characteristics of the 2016 candidate are
displayed in the fourth column of Table 11. Table 12 summarizes the numerical
results obtained in the $K^{+}\rightarrow\pi^{+}\nu\bar{\nu}$ analysis of the
2017 and 2016 independent data samples.

Table 12: Summary from the $K^{+}\rightarrow\pi^{+}\nu\bar{\nu}$ analyses of the data recorded in 2017 and 2016. | 2017 | 2016
---|---|---
Single Event Sensitivity $SES$ | $(0.389\pm 0.024)\times 10^{-10}$ | $(3.15\pm 0.24)\times 10^{-10}$
Expected SM $K^{+}\rightarrow\pi^{+}\nu\bar{\nu}$ decays | $2.16\pm 0.13\pm 0.26_{ext}$ | $0.267\pm 0.20\pm 0.32_{ext}$
Expected background $B\pm\delta_{B}$ | $1.46\pm 0.30$ | $0.15\pm 0.093$
Observed events | $2$ | $1$

The statistical interpretation of the result is obtained from an event
counting approach in the full range of the signal region. The level of the
expected background does not allow a claim of signal observation nor a claim
of inconsistency with the presence of SM $K^{+}\rightarrow\pi^{+}\nu\bar{\nu}$
decays. Therefore both an upper limit and a measurement of the branching ratio
of the $K^{+}\rightarrow\pi^{+}\nu\bar{\nu}$ decay are presented.

A fully frequentist hypothesis test, with a profile likelihood ratio as test
statistic, is used to combine the results of the 2017 and 2016 analyses. The
parameter of interest is the signal strength $\mu$ defined as the branching
ratio in units of the Standard Model one. The nuisance parameters are the
total expected number of background events in the signal regions ($B$) and the
single event sensitivity ($SES$), obtained separately from the 2016 and 2017
datasets. Following the method described in [27] and according to [28], the
number of background events is constrained to follow a Poisson distribution
with mean value $(B/\delta_{B})^{2}$ where $\delta_{B}$ is the uncertainty of
$B$ (Table 12). The mean $(B/\delta_{B})^{2}$ accounts for an equivalent
number of events counted in control regions through the auxiliary measurements
leading to $B$ as described in section 7. A log-normal distribution function
is used to constrain the $SES$ around the measured value.

The likelihood functions of the results of the 2016 and 2017 analyses are
multiplied to form a single combined function, which is profiled with respect
to the nuisance parameters. The upper limit on the branching ratio of the
$K^{+}\rightarrow\pi^{+}\nu\bar{\nu}$ decay is obtained using a
CL${}_{\text{S}}$ method [29] for several values of the signal strength $\mu$
(Figure 25). The 90% CL expected upper limit is
BR$(K^{+}\rightarrow\pi^{+}\nu\bar{\nu})<1.24\times 10^{-10}$ and the observed
one is:

$\text{BR}(K^{+}\rightarrow\pi^{+}\nu\bar{\nu})<1.78\times 10^{-10}.$ (18)

This result translates to a Grossman-Nir limit [30] of the SM
$K_{L}\rightarrow\pi^{0}\nu\bar{\nu}$ branching ratio equal to $7.8\times
10^{-10}$.

Figure 25:  CL${}_{\text{S}}$ $p$-values as a function of the branching ratio
of the $K^{+}\rightarrow\pi^{+}\nu\bar{\nu}$ decay expressed in units of the
Standard Model value. The red (blue) line corresponds to the 90% (95%) CL.

The data also allow the setting of a 68% CL interval on the SM branching ratio
of the $K^{+}\rightarrow\pi^{+}\nu\bar{\nu}$ decay. Using the prescriptions of
[31] and [32], the measured $K^{+}\rightarrow\pi^{+}\nu\bar{\nu}$ branching
ratio is:

$\text{BR}(K^{+}\rightarrow\pi^{+}\nu\bar{\nu})=(0.48^{+0.72}_{-0.48})\times
10^{-10}.$ (19)

##  9 Conclusions

An investigation of $K^{+}\rightarrow\pi^{+}\nu\bar{\nu}$ has been performed
using the data collected by the NA62 experiment at CERN in 2017. The
experiment has reached the best single event sensitivity so far in this decay
mode, corresponding to $(0.389\pm 0.024_{syst})\times 10^{-10}$. This
translates into an expectation of $(2.16\pm 0.13_{syst}\pm 0.26_{ext})$
$K^{+}\rightarrow\pi^{+}\nu\bar{\nu}$ events in the signal regions, assuming
the Standard Model BR of ($8.4\pm 1.0)\times 10^{-11}$. A further 1.5
background events are expected in the same signal regions, mainly due to a
single $\pi^{+}$ produced along the beam line upstream of the $K^{+}$ decay
volume and accidentally matched to a beam kaon. Using a blind analysis
procedure, two candidate events have been observed in the signal regions,
consistent with expectation. These two candidates, together with the single
candidate observed from the analysis of the 2016 data, lead to the most
stringent upper limit on the branching ratio
BR$(K^{+}\rightarrow\pi^{+}\nu\bar{\nu})<1.78\times 10^{-10}$ at 90% CL and
set the Grossman-Nir limit on BR$(K_{L}\rightarrow\pi^{0}\nu\bar{\nu})$ to
$7.8\times 10^{-10}$. The corresponding 68% CL measurement of the
$K^{+}\rightarrow\pi^{+}\nu\bar{\nu}$ branching ratio is
$(0.48^{+0.72}_{-0.48})\times 10^{-10}$. This result constrains some New
Physics models that can predict large enhancements previously allowed by the
measurements published by the E787 and E949 BNL experiments [8, 9, 10, 11, 15,
16]. The NA62 experiment has collected and is now analysing almost twice as
much data in 2018 as that reported upon here, and further optimization of the
analysis strategy is expected significantly to reduce the uncertainty in the
measured BR of the $K^{+}\rightarrow\pi^{+}\nu\bar{\nu}$ decay.

## Acknowledgements

It is a pleasure to express our appreciation to the staff of the CERN
laboratory and the technical staff of the participating laboratories and
universities for their efforts in the operation of the experiment and data
processing.

The cost of the experiment and its auxiliary systems was supported by the
funding agencies of the Collaboration Institutes. We are particularly indebted
to: F.R.S.-FNRS (Fonds de la Recherche Scientifique - FNRS), Belgium; BMES
(Ministry of Education, Youth and Science), Bulgaria; NSERC (Natural Sciences
and Engineering Research Council), funding SAPPJ-2018-0017 Canada; NRC
(National Research Council) contribution to TRIUMF, Canada; MEYS (Ministry of
Education, Youth and Sports), Czech Republic; BMBF (Bundesministerium für
Bildung und Forschung) contracts 05H12UM5, 05H15UMCNA and 05H18UMCNA, Germany;
INFN (Istituto Nazionale di Fisica Nucleare), Italy; MIUR (Ministero
dell’Istruzione, dell’Università e della Ricerca), Italy; CONACyT (Consejo
Nacional de Ciencia y Tecnología), Mexico; IFA (Institute of Atomic Physics)
Romanian CERN-RO No.1/16.03.2016 and Nucleus Programme PN 19 06 01 04,
Romania; INR-RAS (Institute for Nuclear Research of the Russian Academy of
Sciences), Moscow, Russia; JINR (Joint Institute for Nuclear Research), Dubna,
Russia; NRC (National Research Center) “Kurchatov Institute” and MESRF
(Ministry of Education and Science of the Russian Federation), Russia; MESRS
(Ministry of Education, Science, Research and Sport), Slovakia; CERN (European
Organization for Nuclear Research), Switzerland; STFC (Science and Technology
Facilities Council), United Kingdom; NSF (National Science Foundation) Award
Numbers 1506088 and 1806430, U.S.A.; ERC (European Research Council)
“UniversaLepto” advanced grant 268062, “KaonLepton” starting grant 336581,
Europe.

Individuals have received support from: Charles University Research Center
(UNCE/SCI/ 013), Czech Republic; Ministry of Education, Universities and
Research (MIUR “Futuro in ricerca 2012” grant RBFR12JF2Z, Project GAP), Italy;
Russian Foundation for Basic Research (RFBR grants 18-32-00072, 18-32-00245),
Russia; Russian Science Foundation (RSF 19-72-10096), Russia; the Royal
Society (grants UF100308, UF0758946), United Kingdom; STFC (Rutherford
fellowships ST/J00412X/1, ST/M005798/1), United Kingdom; ERC (grants 268062,
336581 and starting grant 802836 “AxScale”); EU Horizon 2020 (Marie
Skłodowska-Curie grants 701386, 842407, 893101).

## References

  * [1] A.J. Buras, D. Buttazzo, J. Girrbach–Noe and R. Knegjens, J. High Energy Phys. 11 (2015) 33.
  * [2] G. Buchalla and A.J. Buras, Nucl. Phys. B 548 (1999) 309.
  * [3] A.J. Buras, M. Gorbahn, U. Haisch and U. Nierste, J. High Energy Phys. 11 (2006) 002.
  * [4] J. Brod, M. Gorbahn and E. Stamou, Phys. Review D 83 (2011) 034030.
  * [5] G. Isidori, F. Mescia and C. Smith, Nucl. Phys. B 718 (2005), 319.
  * [6] F. Mescia and C. Smith, Phys. Review D 76 (2007), 034017.
  * [7] P.A. Zyla et al., Particle Data Group, Progr. Theor. Exp. Phys. 2020 (2020), 083C01.
  * [8] M. Blanke, A.J. Buras and S. Recksiegel, Eur. Phys. J. C 76  (2016) no.4, 182.
  * [9] M. Blanke, A.J. Buras, B. Duling, K. Gemmler and S. Gori, J. High Energy Phys. 03 (2009) 108.
  * [10] A.J. Buras, D. Buttazzo and R. Knegjens, J. High Energy Phys. 11 (2015) 166.
  * [11] J. Aebischer, A.J. Buras and J. Kumar, arXiv:2006.01138 [hep-ph].
  * [12] G. Isidori, F. Mescia, P. Paradisi, C. Smith and S. Trine, J. High Energy Phys. 08 (2006) 064.
  * [13] M. Tanimoto and K. Yamamoto, Progr. Theor. Exp. Phys. 12 (2016) 123B02.
  * [14] T. Blazek and P. Matak, Int. J. Mod. Phys. A 29 (2014) no.27, 1450162.
  * [15] M. Bordone, D. Buttazzo, G. Isidori and J. Monnard, Eur. Phys. J. C 77 (2017) no.9, 618.
  * [16] C. Bobeth and A. J. Buras, J. High Energy Phys. 1802 (2018) 101.
  * [17] S. Fajfer, N. Košnik and L. Vale Silva, Eur. Phys. J. C 78 (2018) no.4, 275.
  * [18] A.V. Artamonov et al., Phys. Rev. Lett. 101 (2008) 191802.
  * [19] A.V. Artamonov et al., Phys. Rev. D 79 (2009) 092004.
  * [20] E. Cortina Gil et al., Phys. Lett. B 791 (2019) 156.
  * [21] E. Cortina Gil et al., J. Instrum. 12 (2017) P05025.
  * [22] R. Ammendola et al., Nucl. Instrum. Meth. A 929 (2019) 1.
  * [23] J. Allison et al., Nucl. Instrum. Methhods A 835 (2016) 186.
  * [24] G. Anzivino et al., J. Instrum. 13 (2018) P07012.
  * [25] G. Aglieri Rinella et al, J. Instrum. 14 (2019) P07010.
  * [26] C. Gatti, Eur. Phys. J. C 45 (2006) 417.
  * [27] K. Cranmer, arXiv:1503.07622 [physics.data-an].
  * [28] R.D. Cousins et al., Nucl. Instrum. Methods A 595 (2008) 480.
  * [29] A.L. Read, J. Phys. G 28 (2002) 2693.
  * [30] Y. Grossman and Y. Nir, Phys. Lett. B 398 (1997) 163.
  * [31] G.J. Feldman and R.D. Cousins, Phys. Rev. D 57 (1998) 3873.
  * [32] W.A. Rolke and A.M. López, Nucl. Instrum. Methods A 458 (2001) 745.