# No Dimensional Sampling Coresets for Classification

Meysam Alishahi<EMAIL_ADDRESS>
Kahlert School of Computing
University of Utah
Salt Lake City, UT 84112, USA Jeff M. Phillips<EMAIL_ADDRESS>
Kahlert School of Computing
University of Utah
Salt Lake City, UT 84112, USA Visiting ScaDS.AI, University of Leipzig, and
MPI for Math in the Sciences

###### Abstract

We refine and generalize what is known about coresets for classification
problems via the sensitivity sampling framework. Such coresets seek the
smallest possible subsets of input data, so one can optimize a loss function
on the coreset and ensure approximation guarantees with respect to the
original data. Our analysis provides the first no dimensional coresets, so the
size does not depend on the dimension. Moreover, our results are general,
apply for distributional input and can use iid samples, so provide sample
complexity bounds, and work for a variety of loss functions. A key tool we
develop is a Radamacher complexity version of the main sensitivity sampling
approach, which can be of independent interest.

Keywords. coreset, classification, sensitivity sampling, Radamacher complexity

##  1 Introduction

In machine learning, coresets (Phillips, 2016) are small subsets of input data
that act as proxy for the full set while _guaranteeing_ not to deviate much in
accuracy. By reducing data size, they improve scalability and efficiency. A
common approach for constructing coresets involves sampling data points with
probabilities proportional to their so-called _sensitivity score_ , a bound on
the worst-case impact that a point can have on the property of interest. In
classification problems, the property optimized is a loss function $\ell$
which is typically a smooth and convex approximation of the misclassification
rate. However, the ultimately goal is not just to optimize the loss function
over the observed data, but to understand how well the classifier will perform
using new data drawn iid from the same (unknown) distribution $P$.

To formalize this, consider a probability distribution $P$ over a set
$\mathcal{X}$. Let $\mathcal{W}$ be the parameter space of potential models,
and then $\ell:\mathcal{X}\times\mathcal{W}\longrightarrow[0,\infty)$ is a
loss (or cost) function defined on a single $x\in\mathcal{X}$. Let
$\int_{x\in\mathcal{X}}\ell(x,w){\rm d}P(x)$ be the full loss function
evaluated at $w\in\mathcal{W}$, which we will seek to minimize. Now a (finite)
set $Y\subseteq\mathcal{X}$ accompanied by a measure (or weight function)
$\nu$, is termed an _$\varepsilon$ -coreset_ for
$(\mathcal{X},P,\mathcal{W},\ell)$ for $\varepsilon\in(0,1)$ when it
approximates $P$ in the following way for each $w\in\mathcal{W}$:

$\Big{|}\int_{\mathcal{X}}\ell(x,w){\rm d}P(x)-\sum_{y\in
Y}\nu(y)\ell(y,w)\Big{|}\leq\varepsilon\int_{\mathcal{X}}\ell(x,w){\rm d}P(x)$

Algorithms for coresets are often described with respect to a finite sample
$X\subset\mathcal{X}$ where we then assume $P$ has support limited to and
uniform over $X$. We will return later to the integral of $P$ definition to
state more general bounds. Then a very common approach to create a coreset is
via sensitivity sampling (Feldman and Langberg, 2011). This samples points
from $X$ proportional to their sensitivity score $s(x)$. Via an importance
sampling argument, one can show the size of the sample $Y$ needed to induce an
$\varepsilon$-coreset grows proportionally to the total sensitivity
$S=\sum_{x\in X}s(x)$.

For classification, consider a non-increasing function
$\phi:\mathbb{R}\longrightarrow(0,\infty)$ and a set
$\mathcal{W}\subseteq\mathbb{R}^{d}$. Define $\ell_{\phi}(x,w)=\phi(\langle
x,w\rangle)$; this aligns with scenarios like Logistic regression when
$\phi(t)=\log(1+e^{-t})$. However, in (Munteanu et al., 2018), it was proven
that certain types of non-increasing functions $\phi$, specifically those
where $\frac{\phi(x)}{\phi(-x)}$ approaches zero as $x$ goes to infinity, can
lead to $\varepsilon$-coresets that encompass all points in $X$ (see Theorem
3.1 in (Tolochinksy et al., 2022) which refines (Munteanu et al., 2018)). To
construct a smaller coreset, some additional problem structure needs to be
introduced. We mostly focus on the natural way of regularizing the problem
(Shalev-Shwartz and Ben-David, 2014), initiated in the context of coresets by
Tolochinksy et al. (2022). For a positive integer $k$, define
$\ell_{k,\phi}(x,w)=\phi(\langle x,w\rangle)+\frac{1}{k}\|w\|^{2}_{2}$. An
$\varepsilon$-coreset for $(X,p,\mathcal{W},\ell_{k,\phi})$ was termed a
_coreset for a monotonic function $\phi$_ (Tolochinksy et al., 2022; Curtin et
al., 2020). Others approached this issue in varied ways. For example, Munteanu
et al. (2018) introduced a complexity measure $\mu(X)$ that quantifies the
hardness of compressing a dataset for logistic regression, and showed
sublinear-sized coresets can be founding depending on this parameter. Their
results were polynomially improved by Mai et al. (2021) in terms of $\mu(X)$
and $d$. Other work (Mirzasoleiman et al., 2020) considers greedily selected
coresets for learning classifiers under incremental gradient descent where
regularization is again needed, but now to ensure strong convexity.

The most studied examples of $\phi$ are:

  * •

_sigmoid function_ : $\sigma(t)=\frac{1}{1+e^{t}}$,

  * •

_logistic function_ : $\operatorname{{\rm logistic}}(t)=\log(1+e^{-t})$,

  * •

_svm loss function_ : $\operatorname{{\rm svm}}(t)=\max(0,1-t)$.

  * •

_ReLU function_ : $\text{ReLU}(t)=\max(0,t)$

##### Main Results.

Before we describe our results in more technical detail, we first summarize
our main contributions.

  * •

We provide the first _no dimensional_ coreset for monotone functions, of size
$O(k^{3}/\varepsilon^{2})$; it has no dependence on dimension $d$. A special
case of our results are in Table 1 with comparisons to prior work; this
includes a $(\sqrt{\log k})$ factor improvement for logistic loss.

  * •

These bounds use a uniform sample from $X$, _and_ apply to iid samples from
unknown distribution $P$; so this provides a true sample complexity bound for
regularized classification.

  * •

We provide a new general sensitivity sampling bound based on Radamacher
complexity (Theorem 2), which leads to these no dimensional bounds, and we
believe will be of general interest.

  * •

We provide a, in our opinion, simpler proof of the main sensitivity sampling
claim using VC dimension (Feldman et al., 2020; Braverman et al., 2021), which
can handle issues of weighted loss functions needed for these results.

Function $\phi$ | Assumption | Sampling | Coreset size | Reference
---|---|---|---|---
$\operatorname{{\rm logistic}}$ |  bounded $\mu(X)$ | sqrt lev. scores | $\begin{array}[]{c}O^{*}\left(\frac{d^{3}\mu^{3}(X)}{\varepsilon^{4}}\right)\\\ O^{*}\left(\frac{\sqrt{n}d^{\frac{3}{2}}\mu(X)}{\varepsilon^{2}}\right)\end{array}$ | Munteanu et al. 2018
$\operatorname{{\rm logistic}},\operatorname{{\rm svm}},\text{ReLU}$ |  bounded $\mu(X)$ |  $\ell_{l}$ Lewis | $\begin{array}[]{c}O\left(\frac{\mu^{2}(X)d\log(d/\varepsilon)}{\varepsilon^{2}}\right)\end{array}$ | Mai et al. 2021
$\operatorname{{\rm logistic}},\operatorname{{\rm svm}}$ | $\begin{array}[]{c}\|x_{i}\|_{2}\leq 1\ \forall i\\\ \text{reg. term: }\frac{1}{k}\|w\|_{2}^{2}\\\ \|w\|_{2}\leq 1\end{array}$ | sensitivity | $\begin{array}[]{c}O^{*}\left(\frac{kd^{2}\log n\log k}{\varepsilon^{2}}\right)\end{array}$ | Tolochinksy et al. 2022
$\sigma$ | $\text{reg. term: }\frac{1}{k}\|w\|_{2}^{2}$ | sensitivity | $\begin{array}[]{c}O^{*}\left(\frac{kd^{2}\log n\log k}{\varepsilon^{2}}\right)\end{array}$ | Tolochinksy et al. 2022
$\operatorname{{\rm logistic}},\operatorname{{\rm svm}}$ | $\begin{array}[]{c}\|x_{i}\|_{2}\leq 1\ \forall i\\\ \text{reg. term: }\frac{1}{k}\|w\|_{2}^{2}\\\\[2.84544pt] \frac{1}{k}\|w\|_{2},\text{ or }\frac{1}{k}\|w\|_{1}\end{array}$ | uniform | $\begin{array}[]{c}O\left(\frac{dk\log k}{\varepsilon^{2}}\right)\end{array}$ | Curtin et al. 2020
$\sigma,\operatorname{{\rm svm}},\text{ReLU}$ | $\begin{array}[]{c}\|x_{i}\|_{2}\leq 1\ \forall i\\\ \text{reg. term: }\frac{1}{k}\|w\|_{2}^{2}\end{array}$ | uniform | $\begin{array}[]{c}O\left(\frac{dk\log k}{\varepsilon^{2}}\right)\\\\[5.69046pt] O\left(\frac{k^{3}}{\varepsilon^{2}}\right)\end{array}$ | $\begin{array}[]{c}\text{Theorems\leavevmode\nobreak\ \ref{thm:coreset_for_sigmoid},\ref{thm:coreset_for_sigmoid_R},\leavevmode\nobreak\ \ref{thm:coreset_for_svm},}\\\ \text{\leavevmode\nobreak\ \ref{thm:coreset_for_svm_d}, and Section\leavevmode\nobreak\ \ref{sec:relu}}\end{array}$
$\operatorname{{\rm logistic}}$ | $\begin{array}[]{c}\|x_{i}\|_{2}\leq 1\ \forall i\\\ \text{reg. term: }\frac{1}{k}\|w\|_{2}^{2}\end{array}$ | uniform | $\begin{array}[]{c}O\left(\frac{dk\sqrt{\log k}}{\varepsilon^{2}}\right)\\\\[5.69046pt] O\left(\frac{k^{3}}{\varepsilon^{2}\sqrt{\log k}}\right)\end{array}$ | Theorems 28, 25
Table 1: Comparison with prior state-of-the-art results. The notation
$O^{*}(\cdot)$ hides some logarithmic factor in terms of given parameters.

###  1.1 Preliminaries

Throughout the paper, we maintain the assumption that $P$ is a probability
measure over $\mathcal{X}$. If $f:\mathcal{X}\longrightarrow[0,\infty)$ is
$P$-integrable, then the _expectation of $f$ with respect to $P$_ is defined
as $\operatorname*{\mathbb{E}}_{x\sim P}(f(x))=\int_{\mathcal{X}}f(x){\rm
d}P$. While this framework is quite broad, the most natural instances stem
from the following two examples.

Discrete:  Let $p$ be a discrete distribution defined over a countable set
$\mathcal{X}=\\{x_{1},x_{2},\ldots\\}\subseteq\mathbb{R}^{d}$. For any subset
$A\subseteq\mathcal{X}$, the probability measure $P(A)$ is computed as the sum
of probabilities of elements in $A$, given by $P(A)=\sum_{a\in A}p(a)$. In
this scenario, given a function $f:\mathcal{X}\longrightarrow[0,\infty)$, the
expectation $\operatorname*{\mathbb{E}}_{x\sim P}(f(x))$ is expressed as
$\int_{\mathcal{X}}f(x){\rm d}P=\sum_{i=1}^{\infty}p(x_{i})f(x_{i})$. The case
that $\mathcal{X}$ is finite falls under this framework when the distribution
$p$ possesses finite support.

Continuous:  Let $p$ be a continuous probability density distribution defined
over $\mathbb{R}^{d}$, and $\boldsymbol{m}$ represents the Lebesgue measure
(or Borel measure) over $\mathbb{R}^{d}$. Then the probability measure $P(A)$
for a measurable set $A$ is computed as $P(A)=\int_{A}p(x){\rm
d}\boldsymbol{m}$.

When $p(x)$ represents a probability density function, the notation $x\sim P$
denotes sampling based on $p$.

If $\mathcal{F}$ is a set of $P$-integrable functions from $\mathcal{X}$ to
$[0,\infty)$ such that $\int f(x){\rm d}P(x)>0$ for all $f\in\mathcal{F}$,
then the tuple $(\mathcal{X},P,\mathcal{F})$ is termed as _positive definite_.
A $P$-integrable function $s\colon\mathcal{X}\longrightarrow(0,\infty)$ is
called an _upper sensitivity function_ for a positive definite tuple
$(\mathcal{X},P,\mathcal{F})$ if

$\sup_{f\in\mathcal{F}}\frac{f(x)}{\int f(z){\rm d}P(z)}\leq
s(x)\quad\quad\text{for almost all }x\in\mathcal{X}.$ (1)

As a reminder, “for almost all $x\in\mathcal{X}$” signifies that the statement
holds for all $x\in\mathcal{X}$ except for a subset of measure zero with
respect to $P$. Given that a subset of measure zero does not affect sampling
or integral outcomes, without loss of generality, we can assume the inequality
holds for all $x\in\mathcal{X}$. It can be done by either setting the value of
each $f\in\mathcal{F}$ to zero for every $x$ in that measure zero subset or by
removing that measure zero subset from $\mathcal{X}$. We maintain this
assumption going forward. The value $S=\int s(x){\rm d}P(x)$ will be referred
to as the _total sensitivity_ for $(\mathcal{X},P,\mathcal{F})$ with respect
to the function $s(\cdot)$. The _sensitivity normalized probability measure_
for $(\mathcal{X},P,\mathcal{F})$ is defined as ${\rm d}Q=\frac{s(x)}{S}{\rm
d}P$ or equivalently $Q(A)=\int_{A}\frac{s(x)}{S}{\rm d}P(x)$ for each
$P$-measurable $A$. Given that $S=\int s(x){\rm d}P(x)$, it follows that $Q$
represents a probability measure over $\mathcal{X}$ since
$\int_{\mathcal{X}}{\rm d}Q(x)=\int_{\mathcal{X}}\frac{s(x)}{S}{\rm d}P(x)=1$.
An _$s$ -sensitivity sample_ from $\mathcal{X}$ with a size of $m$ is a set of
$m$ iid draws $x_{1}\ldots,x_{m}$ from $\mathcal{X}$ based on $Q$ which will
be expressed as as $x_{1:m}\sim Q$. To simplify, one can imagine iid sampling
from $\mathcal{X}$ using the probability distribution
$q(x)=\frac{s(x)}{S}p(x)$. Define the _$s$ -augmented family of
$(\mathcal{X},P,\mathcal{F})$_ as

$\mathcal{T}_{\mathcal{F}}=\left\\{T_{f}(\cdot)=\frac{Sf(\cdot)}{s(\cdot)\int_{\mathcal{X}}f(x){\rm
d}P(x)}\colon f\in\mathcal{F}\right\\}.$ (2)

For each $f\in\mathcal{F}$, $\sup_{x\in\mathcal{X}}T_{f}(x)\leq S$ and

$\operatorname*{\mathbb{E}}_{x\sim
Q}(T_{f}(x))=\int_{\mathcal{X}}\frac{Sf(x)}{s(x)\int_{\mathcal{X}}f(z){\rm
d}P(z)}\frac{s(x)}{S}{\rm d}P(x)=1.$

Thus, for any $f\in\mathcal{F}$,

$\displaystyle\Big{|}\int_{\mathcal{X}}f(x){\rm
d}P(x)-\sum_{i=1}^{m}\frac{Sf(x_{i})}{ms(x_{i})}\Big{|}\leq\varepsilon\int_{\mathcal{X}}f(x){\rm
d}P(x)\Longleftrightarrow\quad\left|1-\frac{1}{m}\sum_{i=1}^{m}T_{f}(x_{i})\right|\leq\varepsilon.$
(3)

The $m$-th Rademacher Complexity of a family $\mathcal{F}$ of functions from
$\mathcal{X}$ to $\mathbb{R}$ with respect to a probability measure $P$ over
$\mathcal{X}$ is given by

$\mathcal{R}^{P}_{m}(\mathcal{F})=\operatornamewithlimits{\operatorname*{\mathbb{E}}}_{x_{1:m}\sim
P}\operatornamewithlimits{\operatorname*{\mathbb{E}}}_{\sigma_{1:m}\sim\\{-1,1\\}}\sup_{f\in\mathcal{F}}\left[\frac{1}{m}\sum_{i=1}^{m}\sigma_{i}f(x_{i})\right],$

were $\sigma_{1:m}\sim\\{-1,1\\}$ denotes $m$ iid samples
$\sigma_{1},\ldots,\sigma_{m}$ uniformly drawn from $\\{-1,1\\}.$ Rademacher
Complexity somehow serves as a more detailed dimension than VC-dimension.

###### Remark 1

We assume, without explicitly stating, that the supremum over the family
$\mathcal{F}$ in this definition is measurable. This assumption is
consistently applied throughout this paper for other suprema over a class of
functions. It is worth noting that while this assumption may not be applicable
to arbitrary function classes, it holds true for the hypothesis sets commonly
encountered in practical machine learning scenarios. For example, when either
$\mathcal{X}$ or $\mathcal{F}$ is countable, this assumption remains valid.
Furthermore, all the specific cases addressed in this work meet this
requirement.

###  1.2 Our Contributions

Our first main result is the following theorem.

###### Theorem 2

Let $(\mathcal{X},P,\mathcal{F})$ be a positive definite tuple and $s(\cdot)$
be an upper sensitivity function with the total sensitivity $S$. For any
$t>0$, an $s$-sensitivity sample from $\mathcal{X}$ of size $m$, with
probability at least $1-2\exp\left(-{\frac{2mt^{2}}{S}}\right)$, satisfies

$\displaystyle\Big{|}\int f(x){\rm
d}P(x)-\sum_{i=1}^{m}\frac{Sf(x_{i})}{ms(x_{i})}\Big{|}(2\mathcal{R}^{q}_{m}(\mathcal{T}_{\mathcal{F}})+t)\int
f(x){\rm d}P(x)\quad\forall f\in\mathcal{F}.$

This theorem, which is pivotal in our new results, is an adaptation of the
central result from (Feldman and Langberg, 2011; Braverman et al., 2021;
Feldman et al., 2020), extensively employed in coreset construction results,
but now centered on Rademacher Complexity instead of VC-dimension.

Given a function $f:\mathcal{X}\longrightarrow[0,\infty)$, for each $r\geq 0$,
the set $\operatorname{\bf range}(f,\succ,r)$ is defined as:

$\operatorname{\bf range}(f,\succ,r)=\\{x\in\mathcal{X}\colon f(x)>r\\}.$

Now, considering a family of non-negative $P$-measurable functions
$\mathcal{F}$, the _$\mathcal{F}$ -linked range space_ (see Joshi et al. 2011)
is defined as $(\mathcal{X},\operatorname{\bf Ranges}(\mathcal{F},\succ))$
where

$\operatorname{\bf Ranges}(\mathcal{F},\succ)=\\{\operatorname{\bf
range}(f,\succ,r)\colon f\in\mathcal{F},r\geq 0\\}.$

Consider a range space $(\mathcal{X},\mathcal{R})$, where $\mathcal{X}$ is the
ground set and $\mathcal{R}$ is a collection of subsets of $\mathcal{X}$. A
subset $Y\subseteq\mathcal{X}$ is said to be shattered by $\mathcal{R}$ if
every subset $Z\subseteq Y$ can be expressed as $Z=Y\cap R$ for some
$R\in\mathcal{R}$. The _VC-dimension of $(\mathcal{X},\mathcal{R})$_ is
defined as the cardinality of the largest subset $Y\subseteq\mathcal{X}$ that
can be shattered by $R$.

###### Theorem 3

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}.$

This theorem, with variants previously shown in (Braverman et al., 2021;
Feldman et al., 2020), are usually constrained by the assumption that
$\mathcal{X}$ is finite, which has been extensively used to construct
coresets. However, in this work we remove this restriction. Section 5
showcases a novel and simple proof for this theorem, leveraging Fubini’s
Theorem (Fubini, 1907)111Fubini’s Theorem is applicable in our context, given
we are dealing with $\sigma$-finite measures.. Moreover, in instances where
Rademacher complexity refines VC-dimension, our new result Theorem 2 provides
improved bounds. Next we describe several applications stemming from these two
theorems.

##### Well-behaved distributions.

We next describe essential problem parameters, generalizing ones used
elsewhere.

###### Definition 4

Let $P$ be a probability measure over $\mathbb{R}^{d}$,
$\phi\colon\mathbb{R}\longrightarrow[0,\infty)$ a non-increasing Lipschitz
function. We say $P$ is _well-behaved_ (w.r.t. $\phi$) if

$\operatorname*{\mathbb{E}}\limits_{x\sim P}\|x\|_{2}^{2}\leq
E^{2}_{1}\quad\text{ and }\quad\operatorname*{\mathbb{E}}\limits_{x\sim
P}\phi\left(\frac{\|x\|_{2}}{2E_{1}}\right)\geq E_{2},$ (4)

for positive constants $E_{1},E_{2}$. For constant $k>0$ define

$\mathcal{L}_{\phi,k}=\left\\{\ell_{\phi,k}(w,\cdot)=\phi(\langle
w,\cdot\rangle)+\frac{\|w\|_{2}^{2}}{k}\colon w\in\mathcal{X}\right\\}.$ (5)

Given
$\operatorname*{\mathbb{E}}(t^{2})\geq\operatorname*{\mathbb{E}}^{2}(t)$, we
can conclude that $\operatorname*{\mathbb{E}}_{x\sim
P}\left(\|x\|_{2}\right)\leq E_{1}$. The assumption on the expectation of
$\|x\|_{2}^{2}$ is fairly standard, such as in bounded or normalized data
where it is an absolute constant. On the other hand, when $p$ is the Gaussian
distribution $\mathcal{N}_{d}(\boldsymbol{0},\boldsymbol{I})$, then $E_{1}=d$.
The lower bound for $\operatorname*{\mathbb{E}}\limits_{x\sim
P}\phi\left(\frac{\|x\|_{2}}{2E_{1}}\right)$ is a constant bounded by
$\phi(1/2)$ when $\phi$ is convex; then we can apply Jensen’s inequality so

$\operatorname*{\mathbb{E}}\limits_{x\sim
P}\phi\left(\frac{\|x\|_{2}}{2E_{1}}\right)\geq\phi\left(\operatorname*{\mathbb{E}}\limits_{x\sim
P}\frac{\|x\|_{2}}{2E_{1}}\right)\geq\phi\left(\frac{1}{2}\right)=E_{2}.$ (6)

##### Connecting to coresets.

Assume that $s(\cdot):\mathcal{X}\longrightarrow(0,\infty)$ is an upper
sensitivity function for a family of functions $\mathcal{F}$ with total value
$S=\int_{\mathcal{X}}s(x){\rm d}P$. Since $\frac{f(x)}{\int f(z){\rm
d}P(z)}\leq s(x)$ for each $f\in\mathcal{F}$, we have $1=\int\frac{f(x)}{\int
f(z){\rm d}P(z)}{\rm d}P(x)\leq\int s(x){\rm d}P(x)=S.$ If we define
$s^{\prime}(\cdot)=s(\cdot)+1$, then
$s^{\prime}:\mathcal{X}\longrightarrow(1,\infty)$ is also an upper sensitivity
function for that family with total value $S^{\prime}=1+S=O(S)$, since $S\geq
1$.

###### Theorem 5

Let $P$ be a well-behaved probability measure over $\mathbb{R}^{d}$. If
$s(\cdot):\mathbb{R}^{d}\longrightarrow(1,\infty)$ is an upper sensitivity
function for $\mathcal{L}_{\phi,k}$ with total sensitivity $S$ and
$m\geq\frac{2S}{\varepsilon^{2}}\left(8C^{2}+S\log\frac{2}{\delta})\right)$,
then 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_{\phi,k})$ with probability at
least $1-\delta$, where
$C=\left(2LE_{1}+\phi(0)\right)\max\left(2E_{1}k,\frac{1}{E_{2}}\right)+8LkE_{1}+1$.

When $E_{1}$ is independent of dimension, such as bounded or normalized data,
this theorem gives an $\varepsilon$-coreset for $(\mathbb{R}^{d},\ P,\
\mathbb{R}^{d},\ \ell_{\phi,k})$ with size _independent of dimension $d$ and
input size $n$_. In contrast, the coresets for (Tolochinksy et al., 2022),
also considering bounded data, used VC-dimension (via Theorem 3), so their
size depends on $d$ and $n$.

##### Bounds for specific $\phi$.

Before describing our bounds for common choices of $\phi$ we examine the
context of prior work by Tolochinksy et al. (2022). They considered absolutely
bounded data with $\|x\|_{2}^{2}\leq 1$; so $E_{1}=1$ and $E_{2}=\phi(1)$. For
simpler notation we define $R$ so that
$\mathcal{W}_{R}=\\{x\in\mathbb{R}^{d}\colon\|w\|_{2}\leq R\\}$. Up to a few
small typos, we summarize their results:

######  Theorem 6 (Tolochinksy et al., 2022)

Let $X=\\{x_{1},\ldots,x_{n}\\}$ be a set of $n$ points in the unit ball of
$\mathbb{R}^{d}$, $\boldsymbol{u}$ be the uniform probability measure over
$X$, and $\varepsilon,\delta\in(0,1)$, $R,k>0$ where $k$ is a sufficiently
large constant. Then $m=O(\frac{t}{\varepsilon^{2}}(d^{2}\log
t+\log\frac{1}{\delta})$ sensitivity samples is, with probability at least
$1-\delta$, an $\varepsilon$-coreset for

  * •

$(X,\boldsymbol{u},\mathbb{R}^{d},\ell_{k,\sigma})$ with $t=(1+k)\log n$.

  * •

$(X,\boldsymbol{u},\mathcal{W}_{R},\ell_{k,\operatorname{{\rm logistic}}})$
with $t=R^{2}(1+Rk)\log n$.

  * •

$(X,\boldsymbol{u},\mathcal{W}_{R},\ell_{k,\operatorname{{\rm svm}}})$ with
$t=R(1+Rk)\log n$.

It should be emphasized that the last two results in Theorem 6 was
successfully improved to $O(\frac{k}{\varepsilon^{2}}(d\log
k+\log\frac{1}{\delta})$ for $\mathcal{W}=\mathbb{R}^{d}$ and
$k=\Theta(n^{1-\kappa})$ for some $\kappa\in(0,1)$ by Curtin et al. (2020).
The strategy utilized by Tolochinksy et al. (2022) and Curtin et al. (2020) to
demonstrate this theorem can be encapsulated as: (1) find an upper bound for
VC-dimension, (2) approximate a sensitivity upper bound and thus the total
sensitivity, (3) sample $m$ points form $X$ according to an appropriate
distribution, and (4) use Theorem 3 to complete the argument. The argument by
Tolochinksy et al. (2022), however, encounters a critical issue. To apply
Theorem 3, we must replace $d$ with the VC-dimension of the linked-range space
of the $s$-augmented family of $(\mathcal{X},P,\mathcal{L}_{\phi,k})$, i.e.
${\rm VCdim}(\operatorname{\bf
Ranges}(\mathcal{T}_{\mathcal{L}_{\phi,k}},\succ))$, while they directly used
the VC-dimension of linked-range space of $\mathcal{F}$ (instead of
$\mathcal{T}_{\mathcal{L}_{\phi,k}}$). Our work addresses this issue in that
it leads to sensitivity functions for which we can compute the VC-dimension of
the augmented function space. Furthermore, by instead bounding Radamacher
complexity in step (1), we can then use our new Theorem 2 in step (4) to
obtain new bounds. These are summarized in Table 2 and the next theorem;
details are in appendix.

###### Theorem 7

Let $P$ be a probability measure over $\mathbb{R}^{d}$. Given the conditions
outlined in the initial $5$ columns of Table 2, any $s$-sensitivity sample
size $m$ (sampling according to the distribution provided in Column 6)
guarantees an $\varepsilon$-coreset for
$(\mathbb{R}^{d},P,\mathbb{R}^{d},\mathcal{L}_{\phi,k})$ with a probability of
at least $1-\delta$.

function $\phi$ | data assumption |  total sens. $S$ |  constant $C$ | sampling | Coreset size | reference
---|---|---|---|---|---|---
$\sigma$ | $\operatorname*{\mathbb{E}}\limits_{x\sim p}\|x\|_{2}^{2}\leq E^{2}_{1}$ | $O(E_{1}^{2}k)$ | $O(E_{1}^{2}k)$ | $p$ | $\frac{2S}{\varepsilon^{2}}(8C^{2}+S\log\frac{2}{\delta})$ |  Theorem 24
$\sigma$ | $\operatorname*{\mathbb{E}}\limits_{x\sim p}\|x\|_{2}^{2}\leq E^{2}_{1}$ | $O(E_{1}^{2}k)$ | $O(1)$ | $p$ | $\frac{CS}{\varepsilon^{2}}\left(d\log S+\log\frac{1}{\delta}\right)$ |  Theorem 25
$\operatorname{{\rm logistic}}$ | $P\left(\|x\|_{2}\geq A\right)=0$ | $O(\frac{A^{2}k}{\sqrt{\log(A^{2}k)}})$ | $O(A^{2}k)$ | $p$ | $\frac{2S}{\varepsilon^{2}}(8C^{2}+S\log\frac{2}{\delta})$ |  Theorem 28
$\operatorname{{\rm logistic}}$ | $P\left(\|x\|_{2}\geq A\right)=0$ | $O(\frac{A^{2}k}{\sqrt{\log(A^{2}k)}})$ | $O(1)$ | $p$ | $\frac{CS}{\varepsilon^{2}}\left(d\log S+\log\frac{1}{\delta}\right)$ |  Theorem 25
$\operatorname{{\rm logistic}}$ | $\operatorname*{\mathbb{E}}\limits_{x\sim p}\|x\|_{2}^{2}\leq E_{1}$ | $O(\frac{E_{1}^{2}k}{\sqrt{\log(E_{1}^{2}k)}})$ | $O(E_{1}^{2}k)$ | $\frac{s}{S}p$ | $\frac{2S}{\varepsilon^{2}}\left(8C^{2}+S\log\frac{2}{\delta})\right)$ |  Theorem 31
$\operatorname{{\rm logistic}}$ | $\operatorname*{\mathbb{E}}\limits_{x\sim p}\|x\|_{2}^{2}\leq E_{1}$ | $O(\frac{E_{1}^{2}k}{\sqrt{\log(E_{1}^{2}k)}})$ | $O(1)$ | $\frac{s}{S}p$ | $\frac{CS}{\varepsilon^{2}}\left(d^{2}\log S+\log\frac{1}{\delta}\right)$ |  Theorem 33
$\operatorname{{\rm svm}}$ | $P\left(\|x\|_{2}\geq A\right)=0$ | $O(A^{2}k)$ | $O(A^{2}k)$ | $p$ | $\frac{2S}{\varepsilon^{2}}(8C^{2}+S\log\frac{2}{\delta})$ |  Theorem 36
$\operatorname{{\rm svm}}$ | $P\left(\|x\|_{2}\geq A\right)=0$ | $O(A^{2}k)$ | $O(1)$ | $p$ | $\frac{CS}{\varepsilon^{2}}\left(d\log S+\log\frac{1}{\delta}\right)$ |  Theorem 38
$\operatorname{{\rm svm}}$ | $\operatorname*{\mathbb{E}}\limits_{x\sim p}\|x\|_{2}^{2}\leq E_{1}$ | $O(E_{1}^{2}k)$ | $O(E_{1}^{2}k)$ | $\frac{s}{S}p$ | $\frac{2S}{\varepsilon^{2}}\left(8C^{2}+S\log\frac{2}{\delta})\right)$ |  Theorem 40
$\operatorname{{\rm svm}}$ | $\operatorname*{\mathbb{E}}\limits_{x\sim p}\|x\|_{2}^{2}\leq E_{1}$ | $O(E_{1}^{2}k)$ | $O(1)$ | $\frac{s}{S}p$ | $\frac{CS}{\varepsilon^{2}}\left(d^{2}\log S+\log\frac{1}{\delta}\right)$ |  Theorem 41
ReLU | $P\left(\|x\|_{2}\geq A\right)=0$ | $O((1+A)^{2}k)$ | $O((1+A)^{2}k)$ | $p$ | $\frac{2S}{\varepsilon^{2}}(8C^{2}+S\log\frac{2}{\delta})$ |  Section 4.4
ReLU | $P\left(\|x\|_{2}\geq A\right)=0$ | $O((1+A)^{2}k)$ | $O(1)$ | $p$ | $\frac{CS}{\varepsilon^{2}}\left(d\log S+\log\frac{1}{\delta}\right)$ |  Section 4.4
ReLU | $\operatorname*{\mathbb{E}}\limits_{x\sim p}\|x\|_{2}^{2}\leq E_{1}$ | $O((1+E_{1})^{2}k)$ | $O((1+E_{1})^{2}k)$ | $\frac{s}{S}p$ | $\frac{2S}{\varepsilon^{2}}\left(8C^{2}+S\log\frac{2}{\delta})\right)$ |  Section 4.4
ReLU | $\operatorname*{\mathbb{E}}\limits_{x\sim p}\|x\|_{2}^{2}\leq E_{1}$ | $O((1+E_{1})^{2}k)$ | $O(1)$ | $\frac{s}{S}p$ | $\frac{CS}{\varepsilon^{2}}\left(d^{2}\log S+\log\frac{1}{\delta}\right)$ |  Section 4.4
Table 2: Coreset size for
$(\mathbb{R}^{d},P,\mathbb{R}^{d},\mathcal{L}_{\phi,k})$; it is common for
$E_{1},A=1$.

##### Sample complexity.

Note that if the sampling column of Table 2 uses $p$, that indicates the total
sensitivity has a constant upper bound, and we can use iid samples from the
unknown distribution $P$. Not only can we avoid the computational issue of
estimating $s$, but these provide sample complexity bounds for the full
(continuous) setting.

###  1.3 Outline

So far, our setting has been restricted to the Euclidean space domain. In
Section 2, we generalize the use of Euclidean inner product with reproducing
kernels, and thus map the framework to reproducing kernel Hilbert spaces.
Subsequently, we introduce the kernelized version of Theorem 5 (Theorem 10),
along with a summary of its consequential results in Table 3. This also allows
us to reproduce the no dimensional sampling result for kernel density
estimates in Theorem 12. Section 3 is devoted to the proof of our main results
depending on Radamacher complexity (Theorem 2), and the proof of the
kernelized generalization to monotonic coresets in Theorem 5. Then Section 4
studies specific choices for the function $\phi$, such as sigmoid, logistic,
svm, and ReLU functions, individually demonstrating the applicability of our
result (Theorem 10) for each. Consequently, the proofs of all the results
listed in Table 2 will be provided in this section. Section 5 contains the
generalized and (in our view) simplified proof of Theorem 3, which gives the
classic sensitivity sampling bound using VC dimension. Finally, we close the
paper with a section discussing related works, followed by a concluding
section.

##  2 Generalized Framework: Reproducing Kernel Hilbert Space

We can establish the validity of our findings in a broader framework by
employing reproducing kernels. In particular, the above-mentioned results are
automatically derived when considering $\mathcal{X}=\mathbb{R}^{d}$ with the
linear kernel $\boldsymbol{K}(x,w)=\langle x,w\rangle$ as a reproducing kernel
Hilbert space $H$. For those less familiar with reproducing kernel Hilbert
spaces, maintaining this latter setting throughout the entire paper is
helpful.

###  2.1 Kernelization of the Results

The kernel method is known as a powerful technique in machine learning that
enables the handling of non-linear relationships in data by implicitly mapping
it to a higher-dimensional space. This flexibility and efficiency make it a
widely used approach, especially in scenarios where linear methods may not be
sufficient. Reproducing kernel Hilbert spaces (RKHS) are intimately connected
to kernel methods. An RKHS is a type of Hilbert space associated with a
positive definite kernel function. In the context of machine learning, we can
think that the input space is mapped into an RKHS through a feature map.
Broadly, the RKHS framework provides a mathematical foundation for
understanding how non-linear relationships in data can be effectively captured
through implicit mappings into higher-dimensional spaces. The key insight in
the context of kernel methods is that the kernel function implicitly
represents the inner product in the Hilbert space, for more see (Mercer, 1909;
Aronszajn, 1950; Boser et al., 1992; Steinwart and Christmann, 2008; Schölkopf
and Smola, 2018). The following definition extends Definition 4 to the context
of RKHD cases.

###### Definition 8

Let $H$ be 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}$,
$P$ a probability measure over $\mathcal{X}$,
$\phi\colon\mathbb{R}\longrightarrow[0,\infty)$ a non-increasing $L$-Lipschitz
function, and $k>0$ a constant. We say $P$ is _well-behaved_ (w.r.t $\phi$ and
$\boldsymbol{K}$) if

$\operatorname*{\mathbb{E}}\limits_{x\sim P}\boldsymbol{K}(x,x)\leq
E^{2}_{1}\qquad\qquad\text{and}\qquad\qquad\operatorname*{\mathbb{E}}\limits_{x\sim
P}\phi\left(\frac{\sqrt{\boldsymbol{K}(x,x)}}{2E_{1}}\right)\geq E_{2},$ (7)

where $E_{1},E_{2}$ are two positive constants. Define

$\mathcal{L}^{H}_{\phi,k}=\left\\{\ell^{H}_{\phi,k}(w,\cdot)=\phi(\boldsymbol{K}(w,\cdot))+\frac{1}{k}\boldsymbol{K}(w,w)\colon
w\in\mathcal{X}\right\\}$ (8)

and

$\bar{\mathcal{L}}^{H}_{\phi,k}=\left\\{\bar{\ell}^{H}_{\phi,k}(w,\cdot)=\phi(-\boldsymbol{K}(w,\cdot))+\frac{1}{k}\boldsymbol{K}(w,w)\colon
w\in\mathcal{X}\right\\}$ (9)

To keep things simpler, we occasionally employ $\|X\|_{H}$ and
$\langle\cdot,\cdot\rangle_{H}$ instead of $\sqrt{\boldsymbol{K}(x,x)}$ and
$\boldsymbol{K}(\cdot,\cdot)$ respectively.

###### Remark 9

Throughout the paper, we mainly focus on coresets for
$\mathcal{L}^{H}_{\phi,k}$. However, we will see that our analysis
effortlessly extends to $\bar{\mathcal{L}}^{H}_{\phi,k}$. This consideration
is insignificant when dealing with the standard inner product as the kernel,
given that $-\langle w,\cdot\rangle=\langle\cdot,-w\rangle$. However, this
property does not hold for kernels in general.

######  Theorem 10 (Theorem 5, Kernelized Representation)

For a well-behaved probability measure $P$ with respect to a Hilbert space $H$
of real-valued functions defined on $\mathcal{X}$ with kernel
$\boldsymbol{K}\colon\mathcal{X}\times\mathcal{X}\longrightarrow\mathbb{R}$,
if $s(\cdot):\mathcal{X}\longrightarrow(1,\infty)$ is an upper sensitivity
function for $\mathcal{L}^{H}_{\phi,k}$ with total sensitivity $S$ and
$m\geq\frac{2S}{\varepsilon^{2}}\left(8C^{2}+S\log\frac{2}{\delta})\right)$,
then 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}_{\phi,k})$ with probability at
least $1-\delta$, where

$C=\left(2LE_{1}+\phi(0)\right)\max\left(2E_{1}k,\frac{1}{E_{2}}\right)+8LkE_{1}+1.$

The statement remains true if we replace $\mathcal{L}^{H}_{\phi,k}$ and
$(\mathcal{X},\ P,\ \mathcal{X},\ \ell^{H}_{\phi,k})$ by
$\bar{\mathcal{L}}^{H}_{\phi,k}$ and $(\mathcal{X},\ P,\ \mathcal{X},\
\bar{\ell}^{H}_{\phi,k})$.

Considering $\mathbb{R}^{d}$ as a Hilbert space equipped with linear kernel,
we derive Theorem 5 as a corollary of this theorem. In the following, we
present various applications derived from this theorem.

###### Theorem 11

Let us consider $H$, a reproducing kernel Hilbert space of real-valued
functions defined on $\mathcal{X}$ with kernel
$\boldsymbol{K}\colon\mathcal{X}\times\mathcal{X}\longrightarrow\mathbb{R}$,
and $P$, a probability measure over $\mathcal{X}$. Given the conditions
outlined in the initial $4$ columns of Table 3, any $s$-sensitivity sample of
size $m$ (sampling according to the distribution provided in Column 5)
guarantees an $\varepsilon$-coreset for
$(\mathcal{X},P,\mathcal{X},\mathcal{L}^{H}_{\phi,k})$ with a probability of
at least $1-\delta$.

The first five columns of each row in Table 3 outline assumptions concerning
$H$ and $P$, while the last two columns detail sample complexity and the
respective theorem in the paper where the result is introduced. Specifically,
under the conditions specified in the initial four columns, a sample of size
$m$ (as per the sampling distribution in Column 5) produces an
$\varepsilon$-coreset with a probability of $1-\delta$. It is worth
emphasizing once more that the utilization of $p$ in Column 5 signifies that
sampling is directly conducted from the data distribution, specifically
through uniform sampling from the provided data points. This eliminates the
necessity for sensitivity computations in this context.

function $\phi$ | data assumption |  total sens. $S$ |  constant $C$ | sampling | Coreset size | reference
---|---|---|---|---|---|---
$\sigma(\pm\cdot)$ | $\operatorname*{\mathbb{E}}\limits_{x\sim P}\|x\|_{H}^{2}\leq E^{2}_{1}$ | $O(E_{1}^{2}k)$ | $O(E_{1}^{2}k)$ | $p$ | $\frac{2S}{\varepsilon^{2}}(8C^{2}+S\log\frac{2}{\delta})$ |  Theorem 24
$\operatorname{{\rm logistic}}(\pm\cdot)$ | $P\left(\|x\|_{H}\geq A\right)=0$ | $O(\frac{A^{2}k}{\sqrt{\log(A^{2}k)}})$ | $O(A^{2}k)$ | $p$ | $\frac{2S}{\varepsilon^{2}}(8C^{2}+S\log\frac{2}{\delta})$ |  Theorem 28
$\operatorname{{\rm logistic}}(\pm\cdot)$ | $\operatorname*{\mathbb{E}}\limits_{x\sim P}\|x\|_{H}^{2}\leq E_{1}$ | $O(\frac{E_{1}^{2}k}{\sqrt{\log(E_{1}^{2}k)}})$ | $O(E_{1}^{2}k)$ | $\frac{s}{S}p$ | $\frac{2S}{\varepsilon^{2}}\left(8C^{2}+S\log\frac{2}{\delta})\right)$ |  Theorem 31
$\operatorname{{\rm svm}}(\pm\cdot)$ | $P\left(\|x\|_{H}\geq A\right)=0$ | $O(A^{2}k)$ | $O(A^{2}k)$ | $p$ | $\frac{2S}{\varepsilon^{2}}(8C^{2}+S\log\frac{2}{\delta})$ |  Theorem 36
$\operatorname{{\rm svm}}(\pm\cdot)$ | $\operatorname*{\mathbb{E}}\limits_{x\sim P}\|x\|_{H}^{2}\leq E_{1}$ | $O(E_{1}^{2}k)$ | $O(E_{1}^{2}k)$ | $\frac{s}{S}p$ | $\frac{2S}{\varepsilon^{2}}\left(8C^{2}+S\log\frac{2}{\delta})\right)$ |  Theorem 40
Table 3: Coreset size for
$(\mathcal{X},P,\mathcal{X},\mathcal{L}^{H}_{\phi,k})$ where $P$ is a
probability measure over $\mathcal{X}$ and $H$ is an RKHS.

####  2.1.1 Kernel Density Estimate

Let $P$ be a probability measure over $\mathbb{R}^{d}$ and
$\boldsymbol{K}:\mathbb{R}^{d}\times\mathbb{R}^{d}\longrightarrow\mathbb{R}$
be a kernel, for instance the Gaussian kernel
$\boldsymbol{K}(x,w)=\exp(-\|x-w\|^{2})$. At any point $w\in\mathbb{R}^{d}$,
the kernel density estimate is defined ad
$\text{KDE}_{P}(w)=\int_{x\in\mathbb{R}^{d}}\boldsymbol{K}(x,w){\rm d}P(x).$
When we have finite number of points $X=\\{x_{1},\ldots,x_{n}\\}$ given as the
data set, we can assume that $P$ is a uniform probability measure over $X$,
i.e., $P(x=x_{i})=\frac{1}{n}$. In this scenario, we use $\text{KDE}_{X}$
instead of $\text{KDE}_{P}$ and and the expression for $\text{KDE}_{X}$ is
given by

$\text{KDE}_{X}(w)=\frac{1}{n}\sum_{x\in X}\boldsymbol{K}(x,w).$

The evaluation of $\text{KDE}_{X}$ demands O(n) time, which can become
impractical for massive datasets. Therefore, a frequently employed approach is
to substitute $X$ with a significantly smaller dataset $Y$, allowing
$\text{KDE}_{Y}$ to function as an approximation for $\text{KDE}_{X}$.
Formally, for a given $\varepsilon\in(0,1)$, we look for a small size $Y$ such
that

$\sup_{w\in\mathbb{R}^{d}}|\text{KDE}_{X}(w)-\text{KDE}_{Y}(w)|\leq\varepsilon.$

This challenge has been thoroughly explored and investigated in various
studies such as (Phillips and Tai, 2020; Tai, 2022; Charikar et al., 2024;
Bobrowski et al., 2017; Taylor, 2018; Gretton et al., 2012; Phillips et al.,
2015; Rinaldo and Wasserman, 2010; Scott, 2015; Silverman, 1986; Zheng and
Phillips, 2015). Our primary result in this context is presented in the
following theorem, restated as Corollary 37 along with its proof.

###### Theorem 12

Let $\boldsymbol{K}:\mathbb{R}^{d}\times\mathbb{R}^{d}\longrightarrow(0,1]$ be
a reproducing kernel, i.e., a kernel associated with an RKHS, and $P$ be a
probability measure over $\mathbb{R}^{d}$. For $\varepsilon,\delta\in(0,1)$,
there exists a universal constant $C$ (independent of $d$ and
$\boldsymbol{K}$) such that if
$m\geq\frac{C}{\varepsilon^{2}}\log\frac{1}{\delta}$, then, with probability
at least $1-\delta$, for any iid random sample $X=\\{x_{1},\ldots,x_{m}\\}$
based on $P$, we have

$\sup_{w\in\mathbb{R}^{d}}|\text{KDE}_{P}(w)-\text{KDE}_{X}(w)|\leq\varepsilon.$

Note that here, we treat $d$ as a variable, and importantly, our bound is
independent of $d$. The Gaussian, Laplacian, and Exponential kernels are
typically chosen for study. Compared to the state-of-the-art results, we can
reproduce the sampling result of $O(1/\varepsilon^{2})$ provided in the
appendix of (Lopez-Paz et al., 2015) (stated with constant probability of
failure $\delta$), which is the same bound as the greedy selection method
(Lacoste-Julien et al., 2015), and is optimal if we do not bound the dimension
(Phillips and Tai, 2018a). Nevertheless, there are some improvements in these
results, including when $d<1/\varepsilon^{2}$, such as works by (Phillips and
Tai, 2018a, 2020; Karnin and Liberty, 2019), and more recent papers by (Tai,
2022; Charikar et al., 2024).

##  3 Main Tools

This section consists of our primary tools and their accompanying proofs
essential for establishing our other key findings.

###  3.1 Proof of Theorem 2

We begin by revisiting McDiarmid’s inequality, which serves as a concentration
inequality that bounds the deviation of a function of several random variables
from its expected value, under the assumption that changing any one of the
variables can only have a limited effect on the function. If
$(\mathcal{X}_{1},\Sigma_{1},P_{1}),\ldots,(\mathcal{X}_{n},\Sigma_{1},P_{n})$
are probability measure spaces, then $P=\prod_{i=1}^{n}P_{i}$ is a probability
measure over $\prod_{i=1}^{n}\mathcal{X}_{i}$. A function
$f:\prod_{i=1}^{n}\mathcal{X}_{i}\longrightarrow\mathbb{R}$ satisfies the
bounded differences property if there are constants $\displaystyle
c_{1},c_{2},\dots,c_{n}$ such that for all $\displaystyle i\in[n]$, and for
all $\displaystyle
x_{1}\in{\mathcal{X}}_{1},\,x_{2}\in{\mathcal{X}}_{2},\,\ldots,\,x_{n}\in{\mathcal{X}}_{n}$

$\displaystyle\sup_{x_{i}^{\prime}\in{\mathcal{X}}_{i}}\left|f(x_{1},\dots,x_{i-1},x_{i},x_{i+1},\ldots,x_{n})-f(x_{1},\dots,x_{i-1},x_{i}^{\prime},x_{i+1},\ldots,x_{n})\right|\leq
c_{i}.$

######  Lemma 13 ( McDiarmid 1989)

Let $\displaystyle f:\prod_{i=1}^{n}\mathcal{X}_{i}\longrightarrow\mathbb{R}$
satisfy the bounded differences property with bounds $\displaystyle
c_{1},c_{2},\dots,c_{n}$. Consider independent random variables
$X_{1},X_{2},\dots,X_{n}$ where $\displaystyle X_{i}\in{\mathcal{X}}_{i}$ for
all $i$. Then, for any $\varepsilon>0$,

$\displaystyle{\text{P}}\left(f(X_{1},X_{2},\ldots,X_{n})-\mathbb{E}[f(X_{1},X_{2},\ldots,X_{n})]\geq\varepsilon\right)\leq\exp\left(-{\frac{2\varepsilon^{2}}{\sum_{i=1}^{n}c_{i}^{2}}}\right).$

We are all set to demonstrate our findings for this subsection

######  Theorem 14 (Theorem 2, Restated)

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$. Any
$s$-sensitivity sample from $\mathcal{X}$ of size $m$, with probability at
least $1-2\exp\left(-{\frac{2mt^{2}}{S^{2}}}\right)$, satisfies

$\left|\int_{x}f(x){\rm
d}P(x)-\sum_{i=1}^{m}\frac{S}{ms(x_{i})}f(x_{i})\right|\leq(2\mathcal{R}^{q}_{m}(\mathcal{T}_{\mathcal{F}})+t)\int_{x}f(x){\rm
d}P(x)\quad\quad\forall f\in\mathcal{F}.$

Proof  In view of Equation (3), we need to show that, for any iid sample
$x_{1},\ldots,x_{m}\in\mathcal{X}$ according to the sensitivity normalized
distribution $q(x)=\frac{s(x)}{S}p(x)$, with probability at least
$1-2\exp\left(-{\frac{2mt^{2}}{S^{2}}}\right)$,

$\sup_{f\in\mathcal{F}}\left|1-\frac{1}{m}\sum_{i=1}^{m}T_{f}(x_{i})\right|\leq
2\mathcal{R}^{q}_{m}(\mathcal{T}_{\mathcal{F}})+t.$

For every $x\in\mathcal{X}$ and $f\in\mathcal{F}$, we have
$\frac{f(x)}{\int_{\mathcal{X}}f(z){\rm d}P(z)}\leq s(x)$ which implies $0\leq
T_{f}(x)=\frac{Sf(x)}{s(x)\int_{\mathcal{X}}f(z){\rm d}P(z)}\leq S$.
Therefore, $\sup\limits_{x\in\mathcal{X}}T_{f}(x)\leq S$. Now, define

$g(x_{1},\ldots,x_{m})=\sup_{f\in\mathcal{F}}\left[1-\frac{1}{m}\sum_{i=1}^{m}T_{f}(x_{i})\right].$

For each $i\in[m]$ and each
$(x_{1}^{\prime},\ldots,x_{m}^{\prime})\in\mathcal{X}^{m}$ such that
$x^{\prime}_{j}=x_{j}$ for $j\neq i$, observe that

$\displaystyle g(x_{1},\ldots,x_{m})-g(x_{1}^{\prime},\ldots,x_{m}^{\prime})$
$\displaystyle=\sup_{f\in\mathcal{F}}\left[1-\frac{1}{m}\sum_{i=1}^{m}T_{f}(x_{i})\right]-\sup_{f\in\mathcal{F}}\left[1-\frac{1}{m}\sum_{i=1}^{m}T_{f}(x^{\prime}_{i})\right]$
$\displaystyle\leq\sup_{f\in\mathcal{F}}\left[\left(1-\frac{1}{m}\sum_{i=1}^{m}T_{f}(x_{i})\right)-\left(1-\frac{1}{m}\sum_{i=1}^{m}T_{f}(x^{\prime}_{i})\right)\right]$
$\displaystyle\leq\sup_{f\in\mathcal{F}}\left(\frac{1}{m}\sum_{i=1}^{m}T_{f}(x_{i})-\frac{1}{m}\sum_{i=1}^{m}T_{f}(x^{\prime}_{i})\right)$
$\displaystyle\leq\sup_{f\in\mathcal{F}}\left|\frac{T_{f}(x_{i})-T_{f}(x^{\prime}_{i})}{m}\right|\leq\frac{S}{m}.$

We can repeat the above argument to show
$g(x_{1},\ldots,x_{m})-g(x_{1}^{\prime},\ldots,x_{m}^{\prime})\leq\frac{S}{m}$.
Thus
$|g(x_{1},\ldots,x_{m})-g(x_{1}^{\prime},\ldots,x_{m}^{\prime})|\leq\frac{S}{m}$.
Therefore, using McDiarmid’s Inequality, with a probability at least
$1-\exp\left(-{\frac{2mt^{2}}{S^{2}}}\right)$, we have

$\sup_{f\in\mathcal{F}}\left[1-\frac{1}{m}\sum_{i=1}^{m}T_{f}(x_{i})\right]\leq\underbrace{\operatorname*{\mathbb{E}}_{x_{1:m}\sim
q}\left(\sup_{f\in\mathcal{F}}\left[1-\frac{1}{m}\sum_{i=1}^{m}T_{f}(x_{i})\right]\right)}_{=A}+t.$

Similarly, we can prove that, with probability at least
$1-\exp\left(-{\frac{2mt^{2}}{S}}\right)$, we have

$\sup_{f\in\mathcal{F}}\left[\frac{1}{m}\sum_{i=1}^{m}T_{f}(x_{i})-1\right]\leq\underbrace{\operatorname*{\mathbb{E}}_{x_{1:m}\sim
q}\left(\sup_{f\in\mathcal{F}}\left[\frac{1}{m}\sum_{i=1}^{m}T_{f}(x_{i})-1\right]\right)}_{=B}+t.$

Consequently, since $A,B\geq 0$, with probability at least
$1-2\exp\left(-{\frac{2mt^{2}}{S^{2}}}\right)$ we have

$\sup_{f\in\mathcal{F}}\left|1-\frac{1}{m}\sum_{i=1}^{m}T_{f}(x_{i})\right|\leq\max\\{A,B\\}+t.$

Let us now deal with $\max\\{A,B\\}$. As $\operatorname*{\mathbb{E}}_{x\sim
q}(T_{f}(x))=1$, we can write

$\displaystyle\operatorname*{\mathbb{E}}_{x_{1:m}\sim
q}\sup_{f\in\mathcal{F}}$
$\displaystyle\left[1-\frac{1}{m}\sum_{i=1}^{m}T_{f}(x_{i})\right]$
$\displaystyle=\operatorname*{\mathbb{E}}_{x_{1:m}\sim
q}\sup_{f\in\mathcal{F}}\left[\operatorname*{\mathbb{E}}_{x^{\prime}_{1:m}\sim
q}\frac{1}{m}\sum_{i=1}^{m}T_{f}(x^{\prime}_{i})-\frac{1}{m}\sum_{i=1}^{m}T_{f}(x_{i})\right]$
$\displaystyle\leq\operatorname*{\mathbb{E}}_{x_{1:m}\sim
q}\operatorname*{\mathbb{E}}_{x^{\prime}_{1:m}\sim
q}\sup_{f\in\mathcal{F}}\left[\frac{1}{m}\sum_{i=1}^{m}T_{f}(x^{\prime}_{i})-\frac{1}{m}\sum_{i=1}^{m}T_{f}(x_{i})\right]$
$\displaystyle(*)\qquad$
$\displaystyle=\operatorname*{\mathbb{E}}_{x_{1:m}\sim
q}\operatorname*{\mathbb{E}}_{x^{\prime}_{1:m}\sim
q}\operatorname*{\mathbb{E}}_{\sigma_{1:m}\sim\\{-1,1\\}}\sup_{f\in\mathcal{F}}\left[\frac{1}{m}\sum_{i=1}^{m}\sigma_{i}\left(T_{f}(x^{\prime}_{i})-T_{f}(x_{i})\right)\right]$
$\displaystyle\leq\operatorname*{\mathbb{E}}_{x_{1:m}\sim
q}\operatorname*{\mathbb{E}}_{x^{\prime}_{1:m}\sim
q}\operatorname*{\mathbb{E}}_{\sigma_{1:m}\sim\\{-1,1\\}}\left(\sup_{f\in\mathcal{F}}\left[\frac{1}{m}\sum_{i=1}^{m}\sigma_{i}T_{f}(x^{\prime}_{i})\right]+\sup_{f\in\mathcal{F}}\left[\frac{1}{m}\sum_{i=1}^{m}-\sigma_{i}T_{f}(x_{i})\right]\right)$
$\displaystyle=2\operatorname*{\mathbb{E}}_{x_{1:m}\sim
q}\operatorname*{\mathbb{E}}_{\sigma_{1:m}\sim\\{-1,1\\}}\sup_{f\in\mathcal{F}}\left[\frac{1}{m}\sum_{i=1}^{m}\sigma_{i}T_{f}(x_{i})\right]$
$\displaystyle=2\mathcal{R}^{q}_{m}(\mathcal{T}_{\mathcal{F}}).$

The equality marked by $(*)$ is true since $\sigma_{i}$ indeed exchanges
$x_{i}$ and $x_{i}^{\prime}$ together, and since they are iid samples from $q$
it cannot change the expectation. With the same approach, we would have

$\operatorname*{\mathbb{E}}_{x_{1:m}\sim
q}\sup_{f\in\mathcal{F}}\left[\frac{1}{m}\sum_{i=1}^{m}T_{f}(x_{i})-1\right]\leq
2\mathcal{R}^{q}_{m}(\mathcal{T}_{\mathcal{F}}),$

which concludes $\max\\{A,B\\}\leq
2\mathcal{R}^{q}_{m}(\mathcal{T}_{\mathcal{F}})$ completing the proof.

###  3.2 Contraction Lemma

When dealing with Rademacher complexity, we can leverage the helpful lemma
known as Talagrand’s Contraction Lemma (refer to Theorem 4.12 in (Ledoux and
Talagrand, 1991)). This lemma, in particular, establishes that
$\mathcal{R}_{m}(\phi\circ\mathcal{F})\leq L\mathcal{R}_{m}(\mathcal{F})$,
where $\phi\colon\mathbb{R}\longrightarrow\mathbb{R}$ is an $L$-Lipschitz
function, and $\phi\circ\mathcal{F}=\\{\phi\circ f\colon f\in\mathcal{F}\\}$.
Our requirement extends beyond this lemma to a generalization.

###### Lemma 15

Let $\Psi:\mathbb{R}^{\geq 0}\longrightarrow\mathbb{R}^{\geq 0}$ be convex and
increasing, $\boldsymbol{T}\subset\mathbb{R}^{m}$ a bounded set, and
$\varepsilon_{1},\ldots,\varepsilon_{m}>0$. For any $1$-Lipschitz functions
$\phi_{i}\colon\mathbb{R}\longrightarrow\mathbb{R}$ with $\phi_{i}(0)=0$ for
each $i\in[m]$, we have

$\operatorname*{\mathbb{E}}_{\varrho_{{}_{1:m}}\sim\prod_{i=1}^{m}\\{\pm\varepsilon_{i}\\}}\Psi\left(\frac{1}{2}\sup_{\boldsymbol{t}\in\boldsymbol{T}}\left|\sum_{i=1}^{m}\varrho_{i}\phi_{i}(t_{i})\right|\right)\leq\operatorname*{\mathbb{E}}_{\varrho_{{}_{1:m}}\sim\prod_{i=1}^{m}\\{\pm\varepsilon_{i}\\}}\Psi\left(\sup_{\boldsymbol{t}\in\boldsymbol{T}}\left|\sum_{i=1}^{m}\varrho_{{}_{i}}t_{i}\right|\right),$

where $\varrho_{{}_{1:m}}\sim\prod_{i=1}^{m}\\{\pm\varepsilon_{i}\\}$ means
$m$ independent samples $\varrho_{{}_{1}},\ldots,\varrho_{{}_{m}}$ such that
each $\varrho_{{}_{i}}$ is uniformly drawn from
$\\{-\varepsilon_{i},\varepsilon_{i}\\}.$

Before turning to the proof of this lemma, note that the only difference
between this lemma and Theorem 4.12 in (Ledoux and Talagrand, 1991) is that
$\varrho_{{}_{i}}$ here takes its value randomly and uniformly in
$\\{+\varepsilon_{i},-\varepsilon_{i}\\}$ rather than $\\{+1,-1\\}$.

Proof [Proof of Lemma 15.] Define
$\bar{\phi}_{i}(t)=\varepsilon_{i}\phi(\frac{1}{\varepsilon_{i}}t)$. Note that
$\bar{\phi}_{i}(0)=0$ and $\bar{\phi}_{i}(t)$ is $1$-Lipschitz since
$\phi_{i}$ is $1$-Lipschitz. Now, applying the original statement of
Talagrand’s Contraction Lemma (Theorem 4.12 in (Ledoux and Talagrand, 1991))
to $\bar{\phi}_{i}$ and
$\bar{\boldsymbol{T}}=\\{(\varepsilon_{1}t_{1},\ldots,\varepsilon_{m}t_{m})\colon(t_{1},\ldots,t_{m})\in\boldsymbol{T}\\}$
we conclude the statement as following:

$\displaystyle\operatorname*{\mathbb{E}}_{\varrho_{{}_{1:m}}\sim\prod_{i=1}^{m}\\{\pm\varepsilon_{i}\\}}\Psi\left(\frac{1}{2}\sup_{\boldsymbol{t}\in\boldsymbol{T}}\left|\sum_{i=1}^{m}\varrho_{i}\phi_{i}(t_{i})\right|\right)$
$\displaystyle=\operatorname*{\mathbb{E}}_{\sigma_{{}_{1:m}}\sim\prod_{i=1}^{m}\\{\pm
1\\}}\Psi\left(\frac{1}{2}\sup_{\bar{\boldsymbol{t}}\in\bar{\boldsymbol{T}}}\left|\sum_{i=1}^{m}\sigma_{i}\bar{\phi}_{i}(\bar{t}_{i})\right|\right)$
(Talagrand’s Contraction Lemma)
$\displaystyle\leq\operatorname*{\mathbb{E}}_{\sigma_{{}_{1:m}}\sim\prod_{i=1}^{m}\\{\pm
1\\}}\Psi\left(\sup_{\bar{\boldsymbol{t}}\in\bar{\boldsymbol{T}}}\left|\sum_{i=1}^{m}\sigma_{i}\bar{t}_{i}\right|\right)$
$\displaystyle=\operatorname*{\mathbb{E}}_{\sigma_{{}_{1:m}}\sim\prod_{i=1}^{m}\\{\pm
1\\}}\Psi\left(\sup_{\boldsymbol{t}\in\boldsymbol{T}}\left|\sum_{i=1}^{m}\sigma_{i}\varepsilon_{i}t_{i}\right|\right)$
$\displaystyle=\operatorname*{\mathbb{E}}_{\varrho_{{}_{1:m}}\sim\prod_{i=1}^{m}\\{\pm\varepsilon_{i}\\}}\Psi\left(\sup_{\boldsymbol{t}\in\boldsymbol{T}}\left|\sum_{i=1}^{m}\varrho_{i}t_{i}\right|\right).$

The next corollary is what we will need in our later analysis.

###### Corollary 16

Let $\boldsymbol{T}\subset\mathbb{R}^{m}$ be a bounded set, and
$\varepsilon_{1},\ldots,\varepsilon_{m}>0$. For any $L$-Lipschitz functions
$\phi_{i}\colon\mathbb{R}\longrightarrow\mathbb{R}$ with $\phi_{i}(0)=0$ for
each $i\in[m]$, we have

$\operatorname*{\mathbb{E}}_{\varrho_{{}_{1:m}}\sim\prod_{i=1}^{m}\\{\pm\varepsilon_{i}\\}}\sup_{\boldsymbol{t}\in\boldsymbol{T}}\left|\sum_{i=1}^{m}\varrho_{{}_{i}}\phi_{i}(t_{i})\right|\leq
2L\operatorname*{\mathbb{E}}_{\varrho_{{}_{1:m}}\sim\prod_{i=1}^{m}\\{\pm\varepsilon_{i}\\}}\sup_{\boldsymbol{t}\in\boldsymbol{T}}\left|\sum_{i=1}^{m}\varrho_{{}_{i}}t_{i}\right|.$

Proof  Setting $\Psi$ as identity and replacing $\phi_{i}$ with
$\frac{\phi_{i}}{L}$, we conclude the result by Lemma 15.

###  3.3 Proof of Theorem 10

This subsection primarily focuses on proving Theorem 10 (and Theorem 5), a
crucial tool enabling us to derive our main results. We start with bounding
the Radamacher complexity of $\mathcal{T}_{\mathcal{F}}$.

###### Lemma 17

For a well-behaved measure $P$ (see Definition 8), if
$s(\cdot):\mathcal{X}\longrightarrow(1,\infty)$ is an upper sensitivity
function for $\mathcal{L}^{H}_{\phi,k}$ with total sensitivity
$S=\int_{\mathcal{X}}s(x){\rm d}P$, then

$\mathcal{R}^{q}_{m}(\mathcal{T}_{\mathcal{L}^{H}_{\phi,k}})\leq
C\sqrt{\frac{S}{m}},$

where
$C=\left(2LE_{1}+\phi(0)\right)\max\left(4E_{1}k,\frac{1}{E_{2}}\right)+8LkE_{1}+1$.
The same statement holds if we replace $\mathcal{L}^{H}_{\phi,k}$ by
$\bar{\mathcal{L}}_{\phi,k}^{H}$.

Proof  Due to similarity, we only work with $\mathcal{L}_{\phi,k}$. We first
show that

$\operatorname*{\mathbb{E}}_{x_{1:m}\sim
q}\operatorname*{\mathbb{E}}_{\sigma_{1:m}\sim\\{-1,1\\}}\left\|\sum_{i=1}^{m}\sigma_{i}\frac{\boldsymbol{K}(x_{i},\cdot)}{s(x_{i})}\right\|_{H}\leq\sqrt{\frac{m}{S}}E_{1}\quad\text{and}\quad\operatorname*{\mathbb{E}}_{x_{1:m}\sim
q}\operatorname*{\mathbb{E}}_{\sigma_{1:m}\sim\\{-1,1\\}}\left|\sum_{i=1}^{m}\sigma_{i}\frac{1}{s(x_{i})}\right|\leq\sqrt{\frac{m}{S}}.$
(10)

Because of the similarity, we only prove the first one. To this end, using
Jensen’s inequality for the concave function $t\mapsto\sqrt{t}$, we obtain

$\displaystyle\operatorname*{\mathbb{E}}_{x_{1:m}\sim
q}\operatorname*{\mathbb{E}}_{\sigma_{1:m}\sim\\{-1,1\\}}$
$\displaystyle\left\|\sum_{i=1}^{m}\sigma_{i}\frac{\boldsymbol{K}(x_{i},\cdot)}{s(x_{i})}\right\|_{H}$
$\displaystyle\leq\sqrt{\operatorname*{\mathbb{E}}_{x_{1:m}\sim
q}\operatorname*{\mathbb{E}}_{\sigma_{1:m}\sim\\{-1,1\\}}\left\|\sum_{i=1}^{m}\sigma_{i}\frac{\boldsymbol{K}(x_{i},\cdot)}{s(x_{i})}\right\|^{2}_{H}}$
$\displaystyle=\sqrt{\operatorname*{\mathbb{E}}_{x_{1:m}\sim
q}\operatorname*{\mathbb{E}}_{\sigma_{1:m}\sim\\{-1,1\\}}\left\langle\sum_{i=1}^{m}\sigma_{i}\frac{\boldsymbol{K}(x_{i},\cdot)}{s(x_{i})},\sum_{i=1}^{m}\sigma_{i}\frac{\boldsymbol{K}(x_{i},\cdot)}{s(x_{i})}\right\rangle_{H}}$
$\displaystyle=\sqrt{\operatorname*{\mathbb{E}}_{x_{1:m}\sim
q}\operatorname*{\mathbb{E}}_{\sigma_{1:m}\sim\\{-1,1\\}}\left[\sum_{i=1}^{m}\sigma_{i}^{2}\frac{\boldsymbol{K}(x_{i},x_{i})}{s(x_{i})^{2}}+\sum_{i\neq
j}\sigma_{i}\sigma_{j}\frac{\boldsymbol{K}(x_{i},x_{j})}{s(x_{i})s(x_{j})}\right]}$
$\displaystyle=\sqrt{\operatorname*{\mathbb{E}}_{x_{1:m}\sim
q}\left[\sum_{i=1}^{m}\frac{\boldsymbol{K}(x_{i},x_{i})}{s^{2}(x_{i})}\right]}$
(since $q(x)=\frac{s(x)}{S}p(x)$)
$\displaystyle=\frac{1}{\sqrt{S}}\sqrt{\operatorname*{\mathbb{E}}_{x_{1:m}\sim
p}\left[\sum_{i=1}^{m}\frac{\boldsymbol{K}(x_{i},x_{i})}{s(x_{i})}\right]}$
(since $s(x)\geq 1$)
$\displaystyle\leq\frac{1}{\sqrt{S}}\sqrt{\operatorname*{\mathbb{E}}_{x_{1:m}\sim
p}\left[\sum_{i=1}^{m}\boldsymbol{K}(x_{i},x_{i})\right]}$
$\displaystyle=\frac{1}{\sqrt{S}}\sqrt{m\operatorname*{\mathbb{E}}_{x\sim
p}\boldsymbol{K}(x,x)}\leq\sqrt{\frac{m}{S}}E_{1}.$

For simplicity set, $f_{w}(x)=\ell_{\phi,k}^{H}(w,x)$ and
$\alpha(w)=\frac{S}{\int_{\mathcal{X}}f_{w}(x){\rm d}P(x)}$. During the proof,
we need some good upper bounds for $\alpha(w)\|w\|_{H}^{2}$ and $\alpha(w)$.
Note that $\int_{\mathcal{X}}f_{w}(x){\rm
d}P(x)=\frac{1}{k}\|w\|_{H}^{2}+\int_{\mathcal{X}}\phi(\boldsymbol{K}(w,x)){\rm
d}P(x)\geq\frac{1}{k}\|w\|_{H}^{2}$ which implies $\alpha(w)\|w\|_{H}^{2}\leq
Sk$. Also,

$\displaystyle\int_{\mathcal{X}}f_{w}(x){\rm d}P(x)$
$\displaystyle=\frac{1}{k}\|w\|_{H}^{2}+\int_{\mathcal{X}}\phi(\boldsymbol{K}(w,x)){\rm
d}P(x)$
$\displaystyle\geq\frac{1}{k}\|w\|_{H}^{2}+\int_{\mathcal{X}}\phi(\|w\|_{H}\|x\|_{H}){\rm
d}P(x)$ ($\phi$ is non-increasing & Cauchy–Schwarz ineq.)
$\displaystyle\geq\left\\{\begin{array}[]{lc}\frac{1}{4E_{1}^{2}k}&\|w\|_{H}\geq\frac{1}{2E_{1}}\\\
\\\ \int_{\mathcal{X}}\phi(\frac{\|x\|_{H}}{2E_{1}}){\rm
d}P(x)&\|w\|_{H}\leq\frac{1}{2E_{1}}\end{array}\right.$
$\displaystyle\geq\left\\{\begin{array}[]{lc}\frac{1}{4E_{1}k}&\|w\|_{H}\geq\frac{1}{2E_{1}}\\\
\\\ E_{2}&\|w\|_{H}\leq\frac{1}{2E_{1}}\end{array}\right.$
$\displaystyle=\min\left(\frac{1}{4E_{1}k},E_{2}\right).$

This concludes $\alpha(w)\leq\max\left(4SE_{1}k,\frac{S}{E_{2}}\right)$ for
each $w$. Note that if $2^{n}\leq\|w\|_{H}\leq 2^{n+1}$, then

$\displaystyle\int_{\mathcal{X}}f_{w}(x){\rm d}P(x)$
$\displaystyle=\frac{1}{k}\|w\|_{H}^{2}+\int_{\mathcal{X}}\phi(\boldsymbol{K}(w,x)){\rm
d}P(x)\geq\frac{2^{2n}}{k}$

which implies $\alpha(w)\leq\frac{kS}{2^{2n}}.$ So, we obtained

$\alpha(w)\leq\left\\{\begin{array}[]{cc}\max\left(4SE_{1}k,\frac{S}{E_{2}}\right)&\|w\|_{2}\leq
1\\\ \frac{kS}{2^{2n}}&2^{n}\leq\|w\|_{H}\leq 2^{n+1}.\end{array}\right.$ (11)

To bound the supremum within the Radamacher complexity, we utilize these
inequalities to partition the parameter space. It is necessary as we want to
use Lemma 16 in which we need a bounded property. Consequently,

$\displaystyle\mathcal{R}^{q}_{m}(\mathcal{T}_{\mathcal{L}_{\phi,k}^{H}})=\ $
$\displaystyle\operatorname*{\mathbb{E}}_{x_{1:m}\sim
q}\operatorname*{\mathbb{E}}_{\sigma_{1:m}\sim\\{-1,1\\}}\sup_{f\in\mathcal{L}_{\phi,k}^{H}}\left[\frac{1}{m}\sum_{i=1}^{m}\sigma_{i}T_{f}(x_{i})\right]$
$\displaystyle=\ $ $\displaystyle\operatorname*{\mathbb{E}}_{x_{1:m}\sim
q}\operatorname*{\mathbb{E}}_{\sigma_{1:m}\sim\\{-1,1\\}}\sup_{w\in\mathcal{X}}\underbrace{\frac{S}{\int_{\mathcal{X}}f_{w}(x){\rm
d}\mu}}_{=\alpha(w)}\left[\frac{1}{m}\sum_{i=1}^{m}\sigma_{i}\frac{f_{w}(x_{i})}{s(x_{i})}\right]$
$\displaystyle=\ $ $\displaystyle\operatorname*{\mathbb{E}}_{x_{1:m}\sim
q}\operatorname*{\mathbb{E}}_{\sigma_{1:m}\sim\\{-1,1\\}}\sup_{w\in\mathcal{X}}\alpha(w)\left[\frac{1}{m}\sum_{i=1}^{m}\sigma_{i}\frac{\phi(\boldsymbol{K}(w,x_{i}))+\frac{1}{k}\|w\|_{H}^{2}}{s(x_{i})}\right]$
$\displaystyle\leq\ $
$\displaystyle\underbrace{\operatorname*{\mathbb{E}}_{x_{1:m}\sim
q}\operatorname*{\mathbb{E}}_{\sigma_{1:m}\sim\\{-1,1\\}}\sup_{w\in\mathcal{X}}\alpha(w)\left|\frac{1}{m}\sum_{i=1}^{m}\sigma_{i}\frac{\phi(\boldsymbol{K}(w,x_{i}))}{s(x_{i})}\right|}_{=M}$
$\displaystyle\quad\quad+\frac{1}{k}\underbrace{\operatorname*{\mathbb{E}}_{x_{1:m}\sim
q}\operatorname*{\mathbb{E}}_{\sigma_{1:m}\sim\\{-1,1\\}}\sup_{w\in\mathcal{X}}\alpha(w)\left|\frac{1}{m}\sum_{i=1}^{m}\sigma_{i}\frac{\|w\|_{H}^{2}}{s(x_{i})}\right|}_{=N}$
$\displaystyle\textbf{($*$)}\quad\leq\ $
$\displaystyle\left[2LE_{1}\max\left(4E_{1}k,\frac{1}{E_{2}}\right)+8LkE_{1}+\max\left(4E_{1}k,\frac{1}{E_{2}}\right)\phi(0)+1\right]\sqrt{\frac{S}{m}}.$

To prove ($*$), we deal with $M$ and $N$ separately. Note that
$\bar{\phi}(\cdot)=\phi(\cdot)-\phi(0)$ is an $L$-Lipschitz functions with
$\bar{\phi}(0)=0$ and thus satisfies the condition of Corollary 16. Note that

$\displaystyle M\leq$
$\displaystyle\underbrace{\operatorname*{\mathbb{E}}_{x_{1:m}\sim
q}\operatorname*{\mathbb{E}}_{\sigma_{1:m}\sim\\{-1,1\\}}\sup_{w\in\mathcal{X}}\alpha(w)\left|\frac{1}{m}\sum_{i=1}^{m}\sigma_{i}\frac{\bar{\phi}(\boldsymbol{K}(w,x_{i}))}{s(x_{i})}\right|}_{=M_{1}}$
$\displaystyle+\underbrace{\operatorname*{\mathbb{E}}_{x_{1:m}\sim
q}\operatorname*{\mathbb{E}}_{\sigma_{1:m}\sim\\{-1,1\\}}\sup_{w\in\mathcal{X}}\alpha(w)\left|\frac{1}{m}\sum_{i=1}^{m}\sigma_{i}\frac{\phi(0)}{s(x_{i})}\right|}_{=M_{2}}$
$\displaystyle\leq$ $\displaystyle
M_{1}+\phi(0)\max\left(4SE_{1}k,\frac{S}{E_{2}}\right)\operatorname*{\mathbb{E}}_{x_{1:m}\sim
q}\operatorname*{\mathbb{E}}_{\sigma_{1:m}\sim\\{-1,1\\}}\left|\frac{1}{m}\sum_{i=1}^{m}\frac{\sigma_{i}}{s(x_{i})}\right|$
$\displaystyle\leq$ $\displaystyle
M_{1}+\sqrt{\frac{S}{m}}\max\left(4E_{1}k,\frac{1}{E_{2}}\right)\phi(0)$
$\displaystyle\text{by\leavevmode\nobreak\ (\ref{ineq:upper})}.$

To upper bound $M_{1}$, define

$M_{1}^{0}=\operatorname*{\mathbb{E}}_{x_{1:m}\sim
q}\operatorname*{\mathbb{E}}_{\sigma_{1:m}\sim\\{-1,1\\}}\sup_{\|w\|_{H}\leq
1}\alpha(w)\left|\frac{1}{m}\sum_{i=1}^{m}\sigma_{i}\frac{\bar{\phi}(\boldsymbol{K}(w,x_{i}))}{s(x_{i})}\right|$

and, for $n\in\mathbb{N}$,

$M_{1}^{n}=\operatorname*{\mathbb{E}}_{x_{1:m}\sim
q}\operatorname*{\mathbb{E}}_{\sigma_{1:m}\sim\\{-1,1\\}}\sup_{2^{n-1}\leq\|w\|\leq
2^{n}}\alpha(w)\left|\frac{1}{m}\sum_{i=1}^{m}\sigma_{i}\frac{\bar{\phi}(\boldsymbol{K}(w,x_{i}))}{s(x_{i})}\right|$

and note that $M_{1}\leq\sum_{n=0}^{\infty}M_{1}^{n}$. We can write

$\displaystyle M_{1}^{0}$
$\displaystyle=\operatorname*{\mathbb{E}}_{x_{1:m}\sim
q}\operatorname*{\mathbb{E}}_{\sigma_{1:m}\sim\\{-1,1\\}}\sup_{\|w\|_{H}\leq
1}\alpha(w)\left|\frac{1}{m}\sum_{i=1}^{m}\sigma_{i}\frac{\bar{\phi}(\boldsymbol{K}(w,x_{i}))}{s(x_{i})}\right|$
(since $\alpha(w)\leq\max(4SE_{1}k,\frac{S}{E_{2}})$)
$\displaystyle\leq\max\left(4SE_{1}k,\frac{S}{E_{2}}\right)\operatorname*{\mathbb{E}}_{x_{1:m}\sim
q}\operatorname*{\mathbb{E}}_{\sigma_{1:m}\sim\\{-1,1\\}}\sup_{\|w\|_{H}\leq
1}\frac{1}{m}\left|\sum_{i=1}^{m}\sigma_{i}\frac{\bar{\phi}(\boldsymbol{K}(w,x_{i}))}{s(x_{i})}\right|$
(Cor. 16 with $\varepsilon_{i}=\frac{1}{s(x_{i})}$) $\displaystyle\leq
2L\max\left(4SE_{1}k,\frac{S}{E_{2}}\right)\operatorname*{\mathbb{E}}_{x_{1:m}\sim
q}\operatorname*{\mathbb{E}}_{\sigma_{1:m}\sim\\{-1,1\\}}\sup_{\|w\|_{H}\leq
1}\left|\frac{1}{m}\sum_{i=1}^{m}\sigma_{i}\frac{\boldsymbol{K}(w,x_{i})}{s(x_{i})}\right|$
$\displaystyle=\frac{2L}{m}\max\left(4SE_{1}k,\frac{S}{E_{2}}\right)\operatorname*{\mathbb{E}}_{x_{1:m}\sim
q}\operatorname*{\mathbb{E}}_{\sigma_{1:m}\sim\\{-1,1\\}}\sup_{\|w\|_{H}\leq
1}\left|\left\langle\boldsymbol{K}(w,\cdot),\sum_{i=1}^{m}\sigma_{i}\frac{\boldsymbol{K}(x_{i},\cdot)}{s(x_{i})}\right\rangle_{H}\right|$
(Cauchy–Schwarz inequality)
$\displaystyle\leq\frac{2L}{m}\max\left(4SE_{1}k,\frac{S}{E_{2}}\right)\operatorname*{\mathbb{E}}_{x_{1:m}\sim
q}\operatorname*{\mathbb{E}}_{\sigma_{1:m}\sim\\{-1,1\\}}\sup_{\|w\|_{H}\leq
1}\|w\|_{H}\left\|\sum_{i=1}^{m}\sigma_{i}\frac{\boldsymbol{K}(x_{i},\cdot)}{s(x_{i})}\right\|_{H}$
$\displaystyle\leq\frac{2L}{m}\max\left(4SE_{1}k,\frac{S}{E_{2}}\right)\operatorname*{\mathbb{E}}_{x_{1:m}\sim
q}\operatorname*{\mathbb{E}}_{\sigma_{1:m}\sim\\{-1,1\\}}\left\|\sum_{i=1}^{m}\sigma_{i}\frac{\boldsymbol{K}(x_{i},\cdot)}{s(x_{i})}\right\|_{H}$
(by (10)) $\displaystyle\leq
2LE_{1}\max\left(4E_{1}k,\frac{1}{E_{2}}\right)\sqrt{\frac{S}{m}}.$

and similarly,

$\displaystyle M_{1}^{n}$
$\displaystyle=\operatorname*{\mathbb{E}}_{x_{1:m}\sim
q}\operatorname*{\mathbb{E}}_{\sigma_{1:m}\sim\\{-1,1\\}}\sup_{2^{n-1}\leq\|w\|_{H}\leq
2^{n}}\alpha(w)\left|\frac{1}{m}\sum_{i=1}^{m}\sigma_{i}\frac{\bar{\phi}(\boldsymbol{K}(w,x_{i}))}{s(x_{i})}\right|$
(Since $\alpha(w)\leq\frac{kS}{2^{2(n-1)}}$)
$\displaystyle\leq\frac{kS}{m4^{n-1}}\operatorname*{\mathbb{E}}_{x_{1:m}\sim
q}\operatorname*{\mathbb{E}}_{\sigma_{1:m}\sim\\{-1,1\\}}\sup_{2^{n-1}\leq\|w\|_{H}\leq
2^{n}}\left|\sum_{i=1}^{m}\sigma_{i}\frac{\bar{\phi}(\boldsymbol{K}(w,x_{i}))}{s(x_{i})}\right|$
(Cor. 16 with $\varepsilon_{i}=\frac{1}{s(x_{i})}$)
$\displaystyle\leq\frac{2LkS}{m4^{n-1}}\operatorname*{\mathbb{E}}_{x_{1:m}\sim
q}\operatorname*{\mathbb{E}}_{\sigma_{1:m}\sim\\{-1,1\\}}\sup_{2^{n-1}\leq\|w\|_{H}\leq
2^{n}}\left|\sum_{i=1}^{m}\sigma_{i}\frac{\boldsymbol{K}(w,x_{i})}{s(x_{i})}\right|$
$\displaystyle=\frac{2LkS}{m4^{n-1}}\operatorname*{\mathbb{E}}_{x_{1:m}\sim
q}\operatorname*{\mathbb{E}}_{\sigma_{1:m}\sim\\{-1,1\\}}\sup_{2^{n-1}\leq\|w\|_{H}\leq
2^{n}}\left|\left\langle\boldsymbol{K}(w,\cdot),\sum_{i=1}^{m}\sigma_{i}\frac{\boldsymbol{K}(x_{i},\cdot)}{s(x_{i})}\right\rangle_{H}\right|$
$\displaystyle\leq\frac{2LkS}{m4^{n-1}}\operatorname*{\mathbb{E}}_{x_{1:m}\sim
q}\operatorname*{\mathbb{E}}_{\sigma_{1:m}\sim\\{-1,1\\}}\sup_{2^{n-1}\leq\|w\|_{H}\leq
2^{n}}\|w\|_{H}\left\|\sum_{i=1}^{m}\sigma_{i}\frac{\boldsymbol{K}(x_{i},\cdot)}{s(x_{i})}\right\|_{H}$
$\displaystyle\leq\frac{LkS}{m2^{n-3}}\operatorname*{\mathbb{E}}_{x_{1:m}\sim
q}\operatorname*{\mathbb{E}}_{\sigma_{1:m}\sim\\{-1,1\\}}\left\|\sum_{i=1}^{m}\sigma_{i}\frac{\boldsymbol{K}(x_{i},\cdot)}{s(x_{i})}\right\|_{H}$
(by (10)) $\displaystyle\leq\frac{LkE_{1}}{2^{n-3}}\sqrt{\frac{S}{m}}.$

Therefore,

$\displaystyle M_{1}$ $\displaystyle\leq
M_{1}^{0}+\sum_{n=1}^{\infty}M_{1}^{n}$ $\displaystyle\leq
2LE_{1}\max\left(2E_{1}k,\frac{1}{E_{2}}\right)\sqrt{\frac{S}{m}}+\sum_{n=1}^{\infty}\frac{LkE_{1}}{2^{n-3}}\sqrt{\frac{S}{m}}$
$\displaystyle=2LE_{1}\max\left(2E_{1}k,\frac{1}{E_{2}}\right)\sqrt{\frac{S}{m}}+8LkE_{1}\sqrt{\frac{S}{m}}$

and thus

$M\leq\left[2LE_{1}\max\left(4E_{1}k,\frac{1}{E_{2}}\right)+8LkE_{1}+\max\left(4E_{1}k,\frac{1}{E_{2}}\right)\phi(0)\right]\sqrt{\frac{S}{m}}.$

To complete the proof, we need to upper bound $N$ which is done as follows

$\displaystyle N$ $\displaystyle=\operatorname*{\mathbb{E}}_{x_{1:m}\sim
q}\operatorname*{\mathbb{E}}_{\sigma_{1:m}\sim\\{-1,1\\}}\sup_{w\in\mathcal{X}}\alpha(w)\left|\frac{1}{m}\sum_{i=1}^{m}\sigma_{i}\frac{\|w\|_{H}^{2}}{s(x_{i})}\right|$
$\displaystyle=\frac{1}{m}\operatorname*{\mathbb{E}}_{x_{1:m}\sim
q}\operatorname*{\mathbb{E}}_{\sigma_{1:m}\sim\\{-1,1\\}}\sup_{w\in\mathbb{R}^{d}}\alpha(w)\|w\|_{H}^{2}\left[\sum_{i=1}^{m}\sigma_{i}\frac{1}{s(x_{i})}\right]$
(since $\alpha(w)\|w\|^{2}\leq Sk$)
$\displaystyle\leq\frac{Sk}{m}\operatorname*{\mathbb{E}}_{x_{1:m}\sim
q}\operatorname*{\mathbb{E}}_{\sigma_{1:k}}\left|\sum_{i=1}^{m}\frac{\sigma_{i}}{s(x_{i})}\right|$
(by (10)) $\displaystyle\leq\sqrt{\frac{S}{m}}k,$

which completes the proof.

We are now in a position to state the following conclusion.

###### Theorem 18

[Theorem 10, Restated] For a well behaved probability measure $P$ (see
Definition 8), if $s(\cdot):\mathcal{X}\longrightarrow(1,\infty)$ is an upper
sensitivity function for $\mathcal{L}^{H}_{\phi,k}$ with total sensitivity $S$
and
$m\geq\frac{2S}{\varepsilon^{2}}\left(8C^{2}+S\log\frac{2}{\delta})\right)$,
then, with probability at least $1-\delta$, 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}_{\phi,k})$, where

$C=(2LE_{1}+\phi(0))\max(4E_{1}k,\frac{1}{E_{2}})+8LkE_{1}+1.$

The statement remains true if we replace $\mathcal{L}^{H}_{\phi,k}$ and
$(\mathcal{X},\ P,\ \mathcal{X},\ \ell^{H}_{\phi,k})$ by
$\bar{\mathcal{L}}^{H}_{\phi,k}$ and $(\mathcal{X},\ P,\ \mathcal{X},\
\bar{\ell}^{H}_{\phi,k})$.

Proof  The proof immediately follows from Theorem 14 and Lemma 17.
When $E_{1}$ is dimension independent, this theorem provides a no-dimensional
$\varepsilon$-coreset for $(\mathbb{R}^{d},\ P,\ \mathbb{R}^{d},\
\ell_{\phi,k})$, that is, whose size is independent of the dimension of the
space. In the following subsection, we present some applications of this
theorem. This theorem holds significant importance in deriving the dimension-
free results outlined in Table 3.

##  4 Coresets for Monotonic Functions

Let $H$ be 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$ a probability measure over $\mathcal{X}$. For a non-increasing
$L$-Lipschitz function $\phi\colon\mathbb{R}\longrightarrow(0,\infty)$, we
remind that
$\ell^{H}_{\phi,k}:\mathcal{X}\times\mathcal{X}\longrightarrow\mathbb{R}$
where
$\ell^{H}_{\phi,k}(x,w)=\phi(\boldsymbol{K}(x,w))+\frac{1}{k}\|w\|_{H}^{2}.$
An $\varepsilon$-coreset for $(\mathcal{X},P,\mathcal{L}^{H}_{\phi,k})$,
called _$\varepsilon$ -coreset for a monotonic function $\phi$ with respect to
$H$_, is a set $X=\\{x_{1},\ldots,x_{m}\\}\subseteq\mathcal{X}$ accompanied by
a measure (or weight function) $\nu$ such that

$\left|\int_{x\in\mathcal{X}}\ell^{H}_{\phi,k}(x,w){\rm
d}P(x)-\sum_{i=1}^{m}\nu(x_{i})\ell^{H}(x_{i},w)\right|\leq\epsilon\int_{x\in\mathcal{X}}\ell^{H}_{\phi,k}(x,w){\rm
d}P(x)\quad\forall w\in\mathcal{X}.$ (12)

We start with a straightforward observation.

###### Lemma 19

If $\phi:\mathbb{R}\longrightarrow(0,\infty)$ is a non-increasing function and
$0<K_{1}\leq K_{2}$, then

$\frac{\phi(-t)+\frac{t^{2}}{K_{1}}}{\phi(t)+\frac{t^{2}}{K_{1}}}\leq\frac{\phi(-t)+\frac{t^{2}}{K_{2}}}{\phi(t)+\frac{t^{2}}{K_{2}}}\quad\quad\text{for
each }t\geq 0.$

Proof  For $t\geq 0$, we should check the inequality

$\left(\phi(-t)+\frac{t^{2}}{K_{1}}\right)\left(\phi(t)+\frac{t^{2}}{K_{2}}\right)\leq\left(\phi(-t)+\frac{t^{2}}{K_{2}}\right)\left(\phi(t)+\frac{t^{2}}{K_{1}}\right)$

which is equivalent to

$\phi(-t)\frac{t^{2}}{K_{2}}+\phi(t)\frac{t^{2}}{K_{1}}\leq\phi(-t)\frac{t^{2}}{K_{1}}+\phi(t)\frac{t^{2}}{K_{2}}$

which is valid since

$\displaystyle\phi(-t)t^{2}\left(\frac{1}{K_{1}}-\frac{1}{K_{2}}\right)+\phi(t)t^{2}\left(\frac{1}{K_{2}}-\frac{1}{K_{1}}\right)$
$\displaystyle=t^{2}\left(\frac{1}{K_{1}}-\frac{1}{K_{2}}\right)\left(\phi(-t)-\phi(t)\right)\geq
0,$

completing the proof.

A version of the lemma described below appears in (Tolochinksy et al., 2022).
We carefully revisit the ideas in their proof in order to extend and enhance
the lemma.

###### Lemma 20

Let $\phi:\mathbb{R}\longrightarrow(0,\infty)$ be a non-increasing function
such that

$\frac{\phi(-\alpha z)+\frac{z^{2}}{k}}{\phi(\alpha
z)+\frac{z^{2}}{k}}\leq\beta(\alpha)\quad\quad 0\leq\alpha\leq B_{1},0\leq
z\leq B_{2}.$ (13)

If we set $M=\phi(-B_{1}B_{2})$, then, for each $x,y,w\in\mathcal{X}$ with
$\|x\|_{H},\|y\|_{H}\leq B_{1},\|w\|_{H}\leq B_{2}$, we have

$\frac{\phi(0)}{M\beta(\|x\|_{H})}\leq\frac{\ell^{H}_{\phi,k}(x,w)}{\ell^{H}_{\phi,k}(y,w)}\qquad\text{and}\qquad\frac{\phi(0)}{M\beta(\|x\|_{H})}\leq\frac{\bar{\ell}^{H}_{\phi,k}(x,w)}{\bar{\ell}^{H}_{\phi,k}(y,w)}.$

If $\phi$ is universally bounded by $M$, then we do not need upper bounds
$B_{1},B_{2}$ for $\alpha,z$ and consequentially do not need upper bounds for
$\|x\|_{H},\|y\|_{H}$, and $\|w\|_{H}$, and the same statement holds.

Proof  Due to similarity, we only prove the lemma for $\ell^{H}_{\phi,k}$.
First, note that as $\phi$ is non-increasing, $\beta(\alpha)\geq 1$ for each
$\alpha$. Consider arbitrary $x,y,w\in\mathcal{X}$ with
$\|x\|_{H},\|y\|_{H}\leq B_{1},\|w\|_{H}\leq B_{2}$. In the following, we deal
with the two different cases $\boldsymbol{K}(x,w)\leq 0$ and
$\boldsymbol{K}(x,w)>0$ separately. If $\boldsymbol{K}(x,w)\leq 0$, then

$\displaystyle\phi(\boldsymbol{K}(y,w))$ $\displaystyle=\phi(\langle
y,w\rangle_{H})$ $\displaystyle\leq\phi(-\|y\|_{H}\|w\|_{H})$ ($\phi$ is non-
increasing along with Cauchy–Schwarz inequality)
$\displaystyle\leq\phi(-B_{1}B_{2})$
$\displaystyle=M=\frac{M}{\phi(0)}\phi(0)$
$\displaystyle\leq\frac{M}{\phi(0)}\phi(\boldsymbol{K}(x,w))$ (since
$\boldsymbol{K}(x,w)\leq 0$ and $\phi$ is non-increasing)

and hence, as $\frac{M}{\phi(0)},\beta(\|x\|_{H})\geq 1$, by adding
$\frac{\|w\|_{H}^{2}}{k}$ to both sides, we obtain

$\ell_{\phi,k}(y,w)\leq\frac{M}{\phi(0)}\ell^{H}_{\phi,k}(x,w)\leq\frac{M}{\phi(0)}\beta(\|x\|_{H})\ell^{H}_{\phi,k}(x,w).$
(14)

Now, assume that $\boldsymbol{K}(x,w)>0$. Similarly,

$\phi(\boldsymbol{K}(y,w))\leq
M\leq\frac{M}{\phi(0)}\phi(-\boldsymbol{K}(x,w))\leq\frac{M}{\phi(0)}\phi(-\|x\|_{H}\|w\|_{H}).$

Again, by adding $\frac{\|w\|_{H}^{2}}{k}$ to the both sides, we have

$\displaystyle\ell^{H}_{\phi,k}(y,w)=\phi(\boldsymbol{K}(y,w))+\frac{\|w\|_{H}^{2}}{k}$
$\displaystyle\leq\frac{M}{\phi(0)}\left(\phi(-\|x\|_{H}\|w\|_{H})+\frac{\|w\|_{H}^{2}}{k}\right)$
(Property 13)
$\displaystyle\leq\frac{M}{\phi(0)}\beta(\|x\|_{H})\left(\phi(\|x\|_{H}\|w\|_{H})+\frac{\|w\|_{H}^{2}}{k}\right)$
(Cauchy-Schwarts Inequality and $\phi$ is non-increasing)
$\displaystyle\leq\frac{M}{\phi(0)}\beta(\|x\|_{H})\underbrace{\left(\phi(\boldsymbol{K}(x,w))+\frac{\|w\|_{H}^{2}}{k}\right)}_{=\ell^{H}_{\phi,k}(x,w)},$

which implies

$\ell^{H}_{\phi,k}(y,w)\leq\frac{M}{\phi(0)}\beta(\|x\|_{H})\ell^{H}_{\phi,k}(x,w).$
(15)

Combining Equations (14) and (15), we obtain the desired inequality.
This lemma provides us with a function
$\gamma(\alpha)=\frac{\phi(0)}{M\beta(\alpha)}\leq 1$ ensuring
$\gamma(\|x\|_{H})\leq\frac{\ell^{H}_{\phi,k}(x,w)}{\ell^{H}_{\phi,k}(y,w)}$.
The subsequent lemma will highlight the usefulness of this function.

###### Lemma 21

Let $P$ be a probability measure over $\mathcal{X}$. Assume that
$\mathcal{W}\subseteq\mathcal{X}$,
$\ell:\mathcal{X}\times\mathcal{X}\longrightarrow(0,\infty)$, and
$\gamma:[0,\infty)\longrightarrow[0,\infty)$ such that
$0<\int_{\mathcal{X}}\gamma(\|x\|_{H}){\rm d}P(x)<\infty$ and

$\gamma(\|x\|_{H})\leq\frac{\ell(x,w)}{\ell(y,w)}\quad\quad\forall
x,y\in\mathcal{X},w\in\mathcal{W}.$ (16)

Then

$s(y)=\frac{1}{\int_{\mathcal{X}}\gamma(\|x\|_{H}){\rm d}P(x)}$

is an upper sensitivity function for $(\mathcal{X},P,\mathcal{L}_{W})$, where
$\mathcal{L}_{\mathcal{W}}=\\{l(\cdot,w)\colon w\in\mathcal{W}\\}.$

Proof  For a $y\in\mathcal{X}$, we have

$\displaystyle\sup_{w\in\mathcal{W}}\frac{\ell(y,w)}{\int_{\mathcal{X}}\ell(x,w){\rm
d}P(x)}$
$\displaystyle=\sup_{w\in\mathcal{W}}\frac{1}{\int_{X}\frac{\ell(x,w)}{\ell(y,w)}{\rm
d}P(x)}$
$\displaystyle\leq\sup_{w\in\mathcal{W}}\frac{1}{\int_{X}\gamma(\|x\|_{H}){\rm
d}P(x)}$ $\displaystyle=\frac{1}{\int_{X}\gamma(\|x\|_{H}){\rm d}P(x)}$

completing the proof.

It is worth noting that the provided upper sensitivity function
$s(y)=\frac{1}{\int_{\mathcal{X}}\gamma(\|x\|){\rm d}P}$ remains constant,
irrespective of $y\in\mathcal{X}$. In a specific scenario where $\gamma$ is
lower bounded by $L$, the function $s(y)=\frac{1}{L}$ serves as an upper
sensitivity function, possessing a total value of $S=\frac{1}{L}$. It is
important to note that when $\phi$ and $k$ grantee Property (16) for
$\ell=\ell^{H}_{\phi,k}$ (like what is established in Lemma 20), then Lemma 21
provides a methodology to calculate the upper sensitivity function and its
total value for $\mathcal{L}^{H}_{\phi,k}$. This enables us to obtain
$s$-sensitivity samples from $\mathcal{X}$, making Theorem 18 (and Theorem 3)
applicable in this context.

###  4.1 Coreset for Sigmoid function

Tolochinksy et al. (2022) examined Property (16) for specific functions
$\phi$. They demonstrated for the sigmoid function
$\sigma(x)=\frac{1}{1+e^{x}}$ that, given $\alpha>0$, there exists a threshold
$k_{\alpha}$ such that for any $k\geq k_{\alpha}$

$\frac{\sigma(-\alpha z)+\frac{z^{2}}{k}}{\sigma(\alpha
z)+\frac{z^{2}}{k}}\leq 66k\alpha\quad\quad\forall z\geq 0.$ (17)

Using this result, they established the first item of Theorem 6 in which, as a
drawback, $k$ should be sufficiently large contingent on the given data points
$\mathcal{X}$. This dependency comes from the role of $k_{\alpha}$ in Equation
(17). In the subsequent lemma, we eliminate this dependency.

###### Lemma 22

For $\sigma(x)=\frac{1}{1+e^{x}}$ and fixed $k>0$, we have

$\frac{\sigma(-\alpha z)+\frac{z^{2}}{k}}{\sigma(\alpha
z)+\frac{z^{2}}{k}}\leq
4\left(1+\max(e,\alpha^{2}k)\right)\quad\quad\forall\alpha,z\geq 0.$

Proof  One can verify that $\sigma:\mathbb{R}\longrightarrow(0,1)$ is a
positive decreasing function and $\sigma^{\prime}(t)=-\sigma(t)\sigma(-t)$.
For a fixed $\alpha>0$, if we set $t=\alpha z$ and $K=\alpha^{2}k$,

$\frac{\sigma(-\alpha z)+\frac{z^{2}}{k}}{\sigma(\alpha
z)+\frac{z^{2}}{k}}=\frac{\sigma(-t)+\frac{t^{2}}{K}}{\sigma(t)+\frac{t^{2}}{K}}\leq\frac{1+\frac{t^{2}}{K}}{\sigma(t)+\frac{t^{2}}{K}}=f(t).$

To find the maximum of $f(t)$ on $(0,\infty)$ in terms of $K$, we begin by
calculating $f^{\prime}(t)$, the derivative of $f$, after factoring out
$1/(\sigma(t)+\frac{t^{2}}{K})^{2}$, as follows:

$\displaystyle\left(\sigma(t)+\frac{t^{2}}{K}\right)^{2}f^{\prime}(t)=$
$\displaystyle\frac{2t}{K}\left(\sigma(t)+\frac{t^{2}}{K}\right)-\left(\sigma^{\prime}(t)+\frac{2t}{K}\right)\left(1+\frac{t^{2}}{K}\right)$
$\displaystyle=$
$\displaystyle\sigma(t)\frac{2t}{K}-\sigma^{\prime}(t)-\frac{2t}{K}-\sigma^{\prime}(t)\frac{t^{2}}{K}$
$\displaystyle=$
$\displaystyle\sigma(t)\frac{2t}{K}+\sigma(t)\sigma(-t)-\frac{2t}{K}+\sigma(t)\sigma(-t)\frac{t^{2}}{K}$
$\displaystyle=$
$\displaystyle\frac{2t}{K}\left(\sigma(t)-1\right)+\sigma(t)\sigma(-t)\left(1+\frac{t^{2}}{K}\right)$
$\displaystyle\text{\footnotesize(since $\sigma(t)+\sigma(-t)=1$)}\quad=$
$\displaystyle-\sigma(-t)\frac{2t}{K}+\sigma(t)\sigma(-t)\left(1+\frac{t^{2}}{K}\right)$
$\displaystyle=$
$\displaystyle\sigma(-t)\left[-\frac{2t}{K}+\sigma(t)\left(1+\frac{t^{2}}{K}\right)\right].$

So, as $(\sigma(t)+t^{2}/K)^{2}>0$, whenever
$\sigma(t)\left(1+\frac{t^{2}}{K}\right)<\frac{2t}{K}$ or equivalently
$\frac{K}{2t}+\frac{t}{2}<1+e^{t},$ $f^{\prime}$ is negative. For

$h(t)=1+e^{t}-\frac{t}{2}-\frac{K}{2t},$

we have

$h^{\prime}(t)=e^{t}-\frac{1}{2}+\frac{K}{2t^{2}}>0\qquad\qquad\text{for each
}t\geq 0.$

This indicates that $h$ is increasing, implying it can have at most one zero.
Since $h$ is negative for small $t$ and positive for large $t$, it follows
that $h$ possesses a unique zero, denoted as $t_{0}$. This implies that $f$ is
decreasing for $t\geq t_{0}$ and increasing for $t\leq t_{0}$, thus attaining
its maximum at $t_{0}$. In the following discussion, we distinguish between
two cases: $K\geq e$ and $K\leq e$. Initially, we focus on bounding
$\sup_{t\in(0,\infty)}\frac{1+\frac{t^{2}}{K}}{\sigma(t)+\frac{t^{2}}{K}}$ for
the scenario where $K\geq e$. Subsequently, we employ this bound, along with a
straightforward observation, to derive a bound for
$\sup_{t\in(0,\infty)}\frac{1+\frac{t^{2}}{K}}{\sigma(t)+\frac{t^{2}}{K}}$
when $K\leq e$.

  1. 1.

Case 1: $\boldsymbol{K\geq e}.$ We start with $t\geq\log K\geq 1$. As $h$ is
increasing

$h(t)\geq h(\log K)=1+K-\frac{\log K}{2}-\frac{K}{2\log K}\geq 1.$

This means that $h$ is positive for $t\geq\log K$. Now, assume that $t\leq
0.5\log K$. Again, because $h$ is increasing, we have

$h(t)\leq h(0.5\log K)\leq 1+\sqrt{K}-\frac{\log K}{4}-\frac{K}{\log K}<0.$

These observations together yield $t_{0}\in\left[0.5\log K,\ \log K\right]$.
Consequently,

$\displaystyle\sup_{t\in(0,\infty)}\frac{1+\frac{t^{2}}{K}}{\sigma(t)+\frac{t^{2}}{K}}$
$\displaystyle=\frac{1+\frac{t_{0}^{2}}{K}}{\sigma(t_{0})+\frac{t_{0}^{2}}{K}}$
$\displaystyle\leq\frac{1+\frac{\log^{2}K}{K}}{\sigma(\log
K)+\frac{\log^{2}K}{4K}}$
$\displaystyle\leq\frac{1+\frac{\log^{2}K}{K}}{\frac{\log^{2}K}{4K}}$
$\displaystyle\leq 4\left(1+\frac{K}{\log^{2}K}\right)\leq 4(1+K).$

  2. 2.

Case 2: $\boldsymbol{K\leq e}.$ Calculation shows that if $0<K_{1}\leq K_{2}$,
then

$\frac{1+\frac{t^{2}}{K_{1}}}{\sigma(t)+\frac{t^{2}}{K_{1}}}\leq\frac{1+\frac{t^{2}}{K_{2}}}{\sigma(t)+\frac{t^{2}}{K_{2}}}\quad\quad\forall
t\geq 0$

which concludes

$\sup_{t\in(0,\infty)}\frac{1+\frac{t^{2}}{K_{1}}}{\sigma(t)+\frac{t^{2}}{K_{1}}}\leq\sup_{t\in(0,\infty)}\frac{1+\frac{t^{2}}{K_{2}}}{\sigma(t)+\frac{t^{2}}{K_{2}}}.$

Consequently, for $K\leq e$,

$\sup_{t\in(0,\infty)}\frac{1+\frac{t^{2}}{K}}{\sigma(t)+\frac{t^{2}}{K}}\leq\sup_{t\in(0,\infty)}\frac{1+\frac{t^{2}}{e}}{\sigma(t)+\frac{t^{2}}{e}}\leq
4(1+e),$

where the right most inequality comes from Case (1).

Putting Cases (1) and (2) together, we obtain

$\displaystyle\max_{t\in[0,t_{0}]}f(t)$
$\displaystyle\leq\left\\{\begin{array}[]{lc}4(1+K)&K\geq e\\\ \\\
4(1+e)&K<e.\end{array}\right.$

So, replacing $K$ with $\alpha^{2}k$, we obtain

$\frac{\sigma(-\alpha z)+\frac{z^{2}}{k}}{\sigma(\alpha
z)+\frac{z^{2}}{k}}\leq\beta(\alpha)=\left\\{\begin{array}[]{cc}4(1+\alpha^{2}k)&\alpha^{2}k\geq
e\\\ \\\ 4(1+e)&\alpha^{2}k\leq
e\end{array}\right.\quad\quad\forall\alpha,z>0.$

Note that for $\alpha=0$ or $z=0$, the inequality is valid as well.

###### Lemma 23

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}.$ Then
$s(x)=60+32kE_{1}^{2}$ is an upper sensitivity function for $(\mathcal{X},\
P,\ \ell^{H}_{\sigma,k})$ and $(\mathcal{X},\ P,\ \bar{\ell}^{H}_{\sigma,k})$.

Proof  Given $\operatorname*{\mathbb{E}}_{x\sim P}(\|x\|_{H}^{2})\leq
E^{2}_{1}$, Markov’s inequality implies that
$\operatorname*{\mathbb{P}}_{x\sim P}(\|x\|_{H}\geq
2E^{2}_{1})\leq\frac{1}{2}$ and consequently
$\operatorname*{\mathbb{P}}_{x\sim P}(\|x\|_{H}\leq
2E^{2}_{1})\geq\frac{1}{2}$ which will be used later to derive inequality
marked by in $(*)$. Since $\sigma$ is universally bounded by $1$. Lemma 22
indicates that Lemma 20 is applicable with

$\beta_{\sigma}(\alpha)=\left\\{\begin{array}[]{cc}4(1+\alpha^{2}k)&\alpha^{2}k\geq
e\\\ \\\ 4(1+e)&\alpha^{2}k\leq e\end{array}\right.$

and for all $x,y,w\in\mathcal{X}$ and $M=1$. Using Lemma 21 with
$\gamma(\|x\|_{H})=\frac{\sigma(0)}{M\beta_{\sigma}(\|x\|_{H})}=\frac{1}{2\beta_{\sigma}(\|x\|_{H})}$,
we conclude that
$s(y)=\frac{2}{\int_{\mathbb{R}^{d}}\frac{1}{\beta_{\sigma}(\|x\|_{H})}{\rm
d}P}$ is an upper sensitivity function for $(\mathcal{X},\ P,\ \mathcal{X},\
\ell^{H}_{\sigma,k})$ and $(\mathcal{X},\ P,\ \mathcal{X},\
\bar{\ell}^{H}_{\sigma,k})$. Note that

$\displaystyle\int_{\mathcal{X}}\frac{1}{\beta_{\sigma}(\|x\|_{H})}{\rm
d}P(x)$ $\displaystyle\geq\int_{\\{x:e\leq k\|x\|_{H}^{2}\leq
2kE^{2}_{1}\\}}\frac{1}{4(1+\|x\|_{H}^{2}k)}{\rm
d}P(x)+\int_{\\{x:k\|x\|_{H}^{2}<e\\}}\frac{1}{4(1+e)}{\rm d}P(x)$
$\displaystyle\geq\frac{1}{4(1+2kE_{1}^{2})}P\left(\left\\{x:\frac{e}{k}\leq\|x\|_{H}^{2}\leq
2E_{1}^{2}\right\\}\right)+\frac{1}{4(1+e)}P\left(\left\\{x:\|x\|_{H}^{2}<\frac{e}{k}\right\\}\right)$
$\displaystyle\geq\operatorname*{\mathbb{P}}\left(\left\\{x:\|x\|_{H}^{2}\leq
2E^{2}_{1}\right\\}\right)\min\left(\frac{1}{4(1+2kE^{2}_{1})},\frac{1}{4(1+e)}\right)$
$\displaystyle(*)\qquad\qquad$
$\displaystyle\geq\frac{1}{2}\min\left(\frac{1}{4(1+2kE^{2}_{1})},\frac{1}{4(1+e)}\right)$
$\displaystyle\geq\frac{1}{8(1+e+2kE^{2}_{1})}\geq\frac{1}{30+16kE_{1}^{2}}.$

This concludes $s(x)=60+32kE_{1}^{2}$ is an upper sensitivity function for
$(\mathcal{X},P,\ell^{H}_{\sigma,k})$ and
$(\mathcal{X},P,\bar{\ell}^{H}_{\sigma,k})$.
Now, we are at a point to put Theorem 10 into action.

######  Theorem 24 (No Dimensional Sigmoid Coreset)

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}$,
$P$ is a probability measure over $\mathcal{X}$ such that
$\operatorname*{\mathbb{E}}\limits_{x\sim p}\|x\|_{H}^{2}\leq E^{2}_{1}$,
$S=60+32kE_{1}^{2}$, and
$C=\left(2E_{1}+\frac{1}{2}\right)\max\left(4E_{1}k,\frac{2}{5}\right)+8kE_{1}+1.$
For $m\geq\frac{2S}{\varepsilon^{2}}(8C^{2}+S\log\frac{2}{\delta})$, any iid
sample $x_{1},\ldots,x_{m}$ from $P$ with weights $u_{i}=\frac{1}{m}$ provides
an $\varepsilon$-coreset for $(\mathcal{X},P,\mathcal{X},\ell^{H}_{\sigma,k})$
(respectively for $(\mathcal{X},P,\mathcal{X},\bar{\ell}^{H}_{\sigma,k})$ )
with probability at least $1-\delta$.

Proof  Lemma 23 indicates that $s(x)=60+32kE^{2}_{1}$ is an upper sensitivity
function. Given that it is a constant function, $s$-sensitivity sampling is
equivalent to sampling according to $P$. Notice that $\sigma$ is a
$1$-Lipschitz function. As $\log(\cdot)$ is a concave function, using Jensen’s
inequality, we have
$\operatorname*{\mathbb{E}}\left(\log\sigma\left(\frac{\|x_{i}\|_{H}}{2E_{1}}\right)\right)\leq\log\operatorname*{\mathbb{E}}\left(\sigma\left(\frac{\|x_{i}\|_{H}}{2E_{1}}\right)\right).$
On the other hand, since $-\log\sigma(t)=\log(1+e^{t})\leq 1+t,$ we have

$\operatorname*{\mathbb{E}}\left(\log\sigma\left(\frac{\|x_{i}\|_{H}}{2E_{1}}\right)\right)\geq-\operatorname*{\mathbb{E}}\left(1+\frac{\|x_{i}\|_{H}}{2E_{1}}\right)=-1-\frac{\operatorname*{\mathbb{E}}\|x_{i}\|_{H}}{2E_{1}}\geq-\frac{3}{2},$

which concludes

$\operatorname*{\mathbb{E}}\left(\sigma\left(\frac{\|x_{i}\|_{H}}{2E_{1}}\right)\right)\geq
e^{\operatorname*{\mathbb{E}}\left(\log\sigma\left(\frac{\|x_{i}\|_{H}}{2E_{1}}\right)\right)}\geq
e^{-\frac{3}{2}}\geq 0.4=E_{2}.$

Hence, $P$ is well behaved (see Definition 8), thereby allowing Theorem 10 to
establish the statement.
While Theorem 24 holds for any reproducing kernel Hilbert space meeting the
specified criteria, the most intriguing instance arises in Hilbert space
$\mathbb{R}^{d}$ equipped with the standard inner product (also known as the
dot product) as its kernel. In this scenario, we can also employ Theorem 3,
which leads to the subsequent theorem.

###### Theorem 25

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}$ and
$S=60+32kE_{1}^{2}$. There is an
$m=O\left(\frac{S}{\varepsilon^{2}}\left(d\log
S+\log\frac{1}{\delta})\right)\right)$ such that any iid sample
$x_{1},\ldots,x_{m}$ from $P$ with weights $u_{i}=\frac{1}{m}$ provides an
$\varepsilon$-coreset for $(\mathbb{R}^{d},P,\mathbb{R}^{d},\ell_{\sigma,k})$
( respectively for $(\mathbb{R}^{d},P,\mathbb{R}^{d},\bar{\ell}_{\sigma,k})$)
with probability at least $1-\delta$.

Proof  Because of similarity, we only prove the statement for
$(\mathbb{R}^{d},P,\mathbb{R}^{d},\ell_{\sigma,k})$. Given that Lemma 23
asserts the constant function $s(x)=60+32kE^{2}_{1}$ as an upper sensitivity
function for $\mathcal{L}_{\sigma,k}$, we deduce $\operatorname{\bf
Ranges}(\mathcal{T}_{\mathcal{L}_{\sigma,k}},\succ)=\operatorname{\bf
Ranges}(\mathcal{L}_{\sigma,k},\succ)$. To clarify, every function in
$\mathcal{T}_{\mathcal{L}_{\sigma,k}}$ is a function in
$\mathcal{L}_{\sigma,k}$ scaled by a positive constant. This implies ${\rm
VCdim}(\operatorname{\bf
Ranges}(\mathcal{T}_{\mathcal{L}_{\sigma,k}},\succ))={\rm
VCdim}(\operatorname{\bf Ranges}(\mathcal{L}_{\sigma,k},\succ)).$ We would
like to remind that

$\mathcal{T}_{{}_{\mathcal{L}_{\sigma,k}}}=\left\\{f_{w}(\cdot)=\frac{\sigma(\langle
w,\cdot\rangle)+\frac{1}{k}\|w\|_{2}^{2}}{s(\cdot)}\colon
w\in\mathbb{R}^{d}\right\\}.$

For an $f_{w}\in\mathcal{L}_{\sigma,k}$ and $r\geq 0$,

$\displaystyle\operatorname{\bf range}(f_{w},\succ,r)$
$\displaystyle=\left\\{x\in\mathbb{R}^{d}\colon f_{w}(x)>r\right\\}$
$\displaystyle=\left\\{x\in\mathbb{R}^{d}\colon\sigma(\langle
x,w\rangle)+\frac{\|w\|^{2}}{k}>r\right\\}$
$\displaystyle=\left\\{x\in\mathbb{R}^{d}\colon\frac{1}{1+e^{\langle
x,w\rangle}}>\underbrace{r-\frac{\|w\|^{2}}{k}}_{=t}\right\\}$
$\displaystyle=\left\\{\begin{array}[]{ll}\mathbb{R}^{d}&t\leq 0\\\
\varnothing&t\geq 1\\\ \left\\{x\in\mathbb{R}^{d}\colon\langle
x,w\rangle<\log(\frac{1}{t}-1)\right\\}&0<t<1,\end{array}\right.$

which concludes that $\operatorname{\bf Ranges}(\mathcal{L}_{\sigma,k},\succ)$
only includes half-spaces, empty set, and the whole space $\mathbb{R}^{d}$.
Therefore, by Radon’s theorem, ${\rm VCdim}(\operatorname{\bf
Ranges}(\mathcal{L}_{\sigma,k},\succ))\leq d+1$ (for a proof, see Lemma 10.3.1
in (Matousek, 2002)). Leveraging Theorem 3, we derive the statement for
$m=O(\frac{S}{\varepsilon^{2}}\left(d\log S+\log\frac{1}{\delta}\right))$,
thereby completing the proof.

Theorems 24 and 25 can be considered as an advancement of the first item of
Theorem 6. Theorem 6 is applicable when $\mathcal{X}$ is a finite set inside
the unit ball, and $m$ is function that is linear in terms of
$\log(|\mathcal{X}|)$ and quadratic in terms $d$, whereas in Theorem 24,
$\mathcal{X}$ can be infinite, and moreover, the presented $m$ remains
constant concerning those parameters (assuming $E_{1}$ is independent of $d$).
Moreover, in Theorem 25, $m$ linearly depends on $d$, whereas in Theorem 6, it
has a quadratic dependence on $d$.

###  4.2 Coreset for Logistic Function

In binary logistic regression, minimizing the negative log-likelihood involves
working with the logistic function $\operatorname{{\rm
logistic}}(t)=\log(1+e^{-t})$. Therefore, having small coresets for logistic
functions holds significant value. In this section, we establish an upper
bound on the size of a coreset for the logistic function.

###### Lemma 26

For $\operatorname{{\rm logistic}}(x)=\log(1+e^{-t})$ and fixed $k>0$, we have

$\frac{\operatorname{{\rm logistic}}(-\alpha
z)+\frac{z^{2}}{k}}{\operatorname{{\rm logistic}}(\alpha
z)+\frac{z^{2}}{k}}\leq\left\\{\begin{array}[]{cc}\frac{85\alpha^{2}k}{\log(\alpha^{2}k)}&\alpha^{2}k\geq
e\\\ \\\ 85&\alpha^{2}k\leq e.\end{array}\right.\quad\quad\forall\alpha,z\geq
0.$

Proof  Simplifying notation, let $\phi(t)=\operatorname{{\rm logistic}}(t)$.
For a given $\alpha>0$, if we set $t=\alpha z$ and $K=\alpha^{2}k$,

$\frac{\phi(-\alpha z)+\frac{z^{2}}{k}}{\phi(\alpha
z)+\frac{z^{2}}{k}}=\frac{\phi(-t)+\frac{t^{2}}{K}}{\phi(t)+\frac{t^{2}}{K}}=f_{K}(t)\quad\quad
t\geq 0.$

Note that $\phi^{\prime}(t)=-\sigma(t)=\frac{-1}{1+e^{t}}$. Upon computing the
derivative of $f_{K}$, we obtain

$\displaystyle\left(\phi(t)+\frac{t^{2}}{K}\right)^{2}f_{K}^{\prime}(t)$
$\displaystyle=\left(-\phi^{\prime}(-t)+\frac{2t}{K}\right)\left(\phi(t)+\frac{t^{2}}{K}\right)-\left(\phi^{\prime}(t)+\frac{2t}{K}\right)\left(\phi(-t)+\frac{t^{2}}{K}\right)$
$\displaystyle=-\phi^{\prime}(-t)\phi(t)-\phi^{\prime}(-t)\frac{t^{2}}{K}+\phi(t)\frac{2t}{K}-\phi^{\prime}(t)\phi(-t)-\phi^{\prime}(t)\frac{t^{2}}{K}-\phi(-t)\frac{2t}{K}$
$\displaystyle=-\left(\phi^{\prime}(-t)\phi(t)+\phi^{\prime}(t)\phi(-t)\right)+\left(\phi(t)-\phi(-t)\right)\frac{2t}{K}-(\phi^{\prime}(t)+\phi^{\prime}(-t))\frac{t^{2}}{K}$
$\displaystyle=\left(\sigma(-t)\phi(t)+\sigma(t)\phi(-t)\right)+\left(\phi(t)-\phi(-t)\right)\frac{2t}{K}+(\underbrace{\sigma(t)+\sigma(-t)}_{=1})\frac{t^{2}}{K}$
$\displaystyle=\left((1-\sigma(t))\phi(t)+\sigma(t)\phi(-t)\right)+\left(\phi(t)-\phi(-t)\right)\frac{2t}{K}+(\underbrace{\sigma(t)+\sigma(-t)}_{=1})\frac{t^{2}}{K}$
$\displaystyle=\phi(t)+\underbrace{\left(\phi(t)-\phi(-t)\right)}_{=-t\leq
0}\left(\frac{2t}{K}-\sigma(t)\right)+\frac{t^{2}}{K}=h(t).$

We investigate the two cases $K\geq e$ and $K\leq e$ separately. First, assume
that $K\geq e$. In the subsequent analysis, our goal is to determine
$0<t_{1}<t_{2}$ such that $h(t)>0$ (equivalently $f_{K}$ is increasing) for
$t\in[0,t_{1}]$ and $h(t)<0$ (equivalently $f_{K}$ is decreasing) for
$t\in[t_{1},\infty)$. This concludes that $f_{K}$ takes its maximum at some
$t_{0}\in[t_{1},t_{2}]$. Considering the formula of $h(t)$, if
$\frac{2t}{K}\leq\sigma(t)$ or equivalently $g_{1}(t)=1+e^{t}-\frac{K}{2t}\leq
0$, then $h(t)$ is positive. Since the function $g_{1}$ is increasing, for
$t\in(0,\ 0.4\log K]$,

$g_{1}(t)\leq g_{1}(0.4\log k)=1+\sqrt[5]{K^{2}}-\frac{5K}{4\log
K}<0\quad\Longrightarrow\quad h(t)>0.$

Thus, $f_{K}$ is increasing for $t\in[0,\ 0.4\log K]$. Note

$h(t)<0\quad\quad\Longleftrightarrow\quad\quad\phi(t)+\frac{t^{2}}{K}<t\left(\frac{2t}{K}-\sigma(t)\right)\quad\quad\Longleftrightarrow\quad\quad
t\sigma(t)+\phi(t)<\frac{t^{2}}{K}.$ (18)

As $t\sigma(t)+\phi(t)<te^{-t}+e^{-t}=e^{-t}(1+t)$, having
$g_{2}(t)=e^{-t}(1+t)-\frac{t^{2}}{K}<0$ implies $h(t)<0.$ One can see that
$g_{2}$ is decreasing and $g_{2}(2\log K)<0$. Therefore, for $t\geq
t_{1}=2\log K$, $g_{2}(t)<0$ and hence $h(t)<0$ which concludes $f$ is
decreasing for $t\geq 2\log K$. So far, we have seen that $f$ is increasing
for $t\in[0,\ 0.4\log K]$ and decreasing for $t\geq 2\log K$, which yields

$\displaystyle\sup_{t\in\left[0,\ \infty\right)}f_{K}(t)$
$\displaystyle=\sup_{t\in\left[0.4\log K,\ 2\log K\right]}f_{K}(t)$
$\displaystyle=\sup_{t\in\left[0.4\log K,\ 2\log
K\right]}\frac{\phi(-t)+\frac{t^{2}}{K}}{\phi(t)+\frac{t^{2}}{K}}$
$\displaystyle\leq\frac{\phi(-2\log K)+\frac{(2\log
K)^{2}}{K}}{\frac{4\log^{2}K}{25K}}$ (since $\phi(-t)\leq 1+t$)
$\displaystyle\leq\frac{1+2\log
K+\frac{4\log^{2}K}{K}}{\frac{4\log^{2}K}{25K}}$
$\displaystyle=\frac{25K}{4\log^{2}K}+\frac{25K}{2\log K}+25$
$\displaystyle\leq 25+\frac{75K}{4\log K}.$

Up to this point, we have established $\sup_{t\in[0,\ \infty)}f_{K}(t)\leq
25+\frac{75K}{4\log K}$ under the condition that $K\geq e$. To conclude the
argument, we need to determine an upper bound for $\sup_{t\in[0,\
\infty)}f_{K}(t)$ when $0<K\leq e$. Utilizing Lemma 19, for $0<K\leq e$, we
deduce

$\sup_{t\in[0,\ \infty)}f_{K}(t)\leq\sup_{t\in[0,\ \infty)}f_{e}(t)\leq
25+\frac{75e}{4}\leq 85$

which concludes

$\displaystyle\sup_{t\in[0,\ \infty)}f_{K}(t)$
$\displaystyle\leq\left\\{\begin{array}[]{cc}25+\frac{75K}{4\log K}&K\geq e\\\
\\\ 85&K\leq e\end{array}\right.$
$\displaystyle\leq\left\\{\begin{array}[]{cc}\frac{85\alpha^{2}k}{\log(\alpha^{2}k)}&\alpha^{2}k\geq
e\\\ \\\ 85&\alpha^{2}k\leq e.\end{array}\right.$

###### Lemma 27

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
$P\left(\left\\{x\in\mathcal{X}\colon\|x\|_{H}\geq A\right\\}\right)=0$. Then
$s(y)=1+\frac{340(1+kA^{2})}{\sqrt{\max(1,\log(kA^{2}))}}$ is an upper
sensitivity function for $(\mathcal{X},P,\mathcal{L}_{\operatorname{{\rm
logistic}}})$ and $(\mathcal{X},P,\bar{\mathcal{L}}_{\operatorname{{\rm
logistic}}})$.

Proof  As $P\left(\left\\{x\in\mathcal{X}\colon\|x\|_{H}\geq
A\right\\}\right)=0$, we only need to determine $s(y)$ for $y$ with
$\|y\|_{H}\leq A$. Henceforth, we assume that $\|y\|_{H}\leq A$. For
$w\in\mathcal{W}=\\{w\in\mathcal{X}\colon\|w\|_{H}\leq\frac{1}{A}\sqrt{\max(1,\log(A^{2}k))}\\}$,
Lemma 26 indicates that Lemma 20 is applicable with
$B_{1}=A,B_{2}=\frac{1}{A}\sqrt{\max(1,\log(A^{2}k))},\phi(-B_{1}B_{2})\leq
1+\sqrt{\max(1,\log(A^{2}k))}=M$, and

$\beta_{\operatorname{{\rm
logistic}}}(\alpha)=\left\\{\begin{array}[]{cc}\frac{85\alpha^{2}k}{\log(\alpha^{2}k)}&\alpha^{2}k\geq
e\\\ \\\ 85&\alpha^{2}k\geq e.\end{array}\right.$

Using Lemma 21 with $\gamma(\|x\|_{H})=\frac{\operatorname{{\rm
logistic}}(0)}{M\beta_{\operatorname{{\rm
logistic}}}(\|x\|_{H})}\geq\frac{1}{2M\beta_{\operatorname{{\rm
logistic}}}(\|x\|_{H})}$, we conclude that

$\sup_{\|w\|_{H}\leq B_{2}}\frac{\ell^{H}_{{}_{\operatorname{{\rm
logistic}},k}}(y,w)}{\int_{x\in\mathcal{X}}\ell^{H}_{{}_{\operatorname{{\rm
logistic}},k}}(x,w){\rm
d}P(x)}\leq\frac{2M}{\int_{x\in\mathcal{X}}\frac{1}{\beta_{\operatorname{{\rm
logistic}}}(\|x\|_{H})}{\rm d}P(x)}.$

Note that

$\displaystyle\int_{x\in\mathcal{X}}\frac{1}{\beta_{\operatorname{{\rm
logistic}}}(\|x\|_{H})}{\rm d}P(x)$ $\displaystyle\geq\int_{\\{x:e\leq
k\|x\|_{H}^{2}\\}}\frac{\log(k\|x\|_{H}^{2})}{85k\|x\|_{H}^{2}}{\rm
d}P(x)+\int_{\\{x:k\|x\|_{H}^{2}<e\\}}\frac{1}{85}{\rm d}P(x)$
$\displaystyle\geq\frac{\log(kA^{2})}{85kA^{2}}P\left(\left\\{x:\frac{e}{k}\leq\|x\|_{H}^{2}\right\\}\right)+\frac{1}{85}P\left(\left\\{x:\|x\|_{H}^{2}<\frac{e}{k}\right\\}\right)$
$\displaystyle\geq\left\\{\begin{array}[]{cc}\frac{\log(kA^{2})}{85kA^{2}}&A^{2}k\geq
e\\\ \\\ \frac{1}{85}&A^{2}k<e\end{array}\right.$
$\displaystyle\geq\frac{\max(1,\log(kA^{2}))}{85(1+kA^{2})}.$

This concludes

$\displaystyle\sup_{\|w\|_{H}\leq B_{2}}\frac{\ell^{H}_{{}_{\operatorname{{\rm
logistic}},k}}(y,w)}{\int_{x\in\mathcal{X}}\ell^{H}_{{}_{\operatorname{{\rm
logistic}},k}}(x,w){\rm d}P(x)}$
$\displaystyle\leq\frac{170(1+kA^{2})}{\max(1,\log(kA^{2}))}\left(1+\sqrt{\max(1,\log(kA^{2}))}\right)$
$\displaystyle\leq\frac{340(1+kA^{2})}{\sqrt{\max(1,\log(kA^{2}))}}.$

As $\int_{x\in\mathcal{X}}\ell_{{}_{\operatorname{{\rm logistic}},k}}(x,w){\rm
d}P\geq\frac{1}{k}\|w\|_{H}^{2}$, we have

$\displaystyle\sup_{\|w\|_{H}\geq B_{2}}\frac{\ell_{{}_{\operatorname{{\rm
logistic}},k}}(y,w)}{\int_{x\in\mathcal{X}}\ell_{{}_{\operatorname{{\rm
logistic}},k}}(x,w){\rm d}P}$ $\displaystyle\leq\sup_{\|w\|\geq
B_{2}}\frac{\frac{1}{k}\|w\|^{2}+\log(1+e^{-\langle
y,w\rangle})}{\frac{1}{k}\|w\|^{2}}$ $\displaystyle\leq\sup_{\|w\|_{H}\geq
B_{2}}\left[1+\frac{k}{\|w\|_{H}^{2}}\log(1+e^{-\langle y,w\rangle})\right]$
$\displaystyle\leq\sup_{\|w\|_{H}\geq
B_{2}}\left[1+\frac{k}{\|w\|_{H}^{2}}\log(1+e^{\|y\|_{H}\|w\|_{H}})\right]$
(since $\log(1+e^{t})\leq 1+t$ for $t\geq 0$)
$\displaystyle\leq\sup_{\|w\|_{H}\geq
B_{2}}\left[1+\frac{k}{\|w\|_{H}^{2}}\left(1+\|y\|_{H}\|w\|_{H}\right)\right]$
(since $\|w\|_{H}\geq B_{2}$ and $\|y\|_{H}\leq A$) $\displaystyle\leq
1+\frac{kA^{2}}{\max(1,\log(A^{2}k))}+\frac{kA^{2}}{\sqrt{\max(1,\log(A^{2}k))}}$
$\displaystyle\leq 1+\frac{2kA^{2}}{\sqrt{\max(1,\log(A^{2}k))}}.$

So, $s(y)=1+\frac{340(1+kA^{2})}{\sqrt{\max(1,\log(kA^{2}))}}$ is an upper
sensitivity function for $(\mathcal{X},P,\mathcal{L}^{H}_{\operatorname{{\rm
logistic}},k})$. The proof for
$(\mathcal{X},P,\bar{\mathcal{L}}^{H}_{\operatorname{{\rm logistic}},k})$
proceeds in a similar manner.

######  Theorem 28 (No Dimensional Logistic Coreset)

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}$,
$P$ is probability measure over $\mathcal{X}$ such that
$P\left(\left\\{x\in\mathcal{X}\colon\|x\|_{H}\geq A\right\\}\right)=0$,
$S=1+\frac{340(1+kA^{2})}{\sqrt{\max(1,\log(kA^{2}))}}$, and
$C=(2A+1)\max(4Ak,2.5)+8Ak+1$. For
$m\geq\frac{2S}{\varepsilon^{2}}(8C^{2}+S\log\frac{2}{\delta})$, any iid
sample $x_{1},\ldots,x_{m}\in\mathcal{X}$ according to $P$ with weights
$u_{i}=\frac{1}{m}$ provides an $\varepsilon$-coreset for
$(\mathcal{X},P,\mathcal{X},\ell^{H}_{\operatorname{{\rm logistic}},k})$
(respectively for
$(\mathcal{X},P,\mathcal{X},\bar{\ell}^{H}_{\operatorname{{\rm logistic}},k})$
) with probability at least $1-\delta$.

Proof  Lemma 27 asserts that
$s(y)=1+\frac{340(1+kA^{2})}{\sqrt{\max(1,\log(kA^{2}))}}$ serves as an upper
sensitivity function for $(\mathcal{X},\ P,\
\mathcal{L}^{H}_{\operatorname{{\rm logistic}},k})$ and
$(\mathcal{X},P,\mathcal{X},\bar{\ell}^{H}_{\operatorname{{\rm
logistic}},k})$. Since it is a constant function, $s$-sensitivity sampling is
equivalent to sampling according to $P$. It is worth noting that
$\operatorname{{\rm logistic}}$ is a $1$-Lipschitz, convex, and decreasing
function. For $E_{1}=A$, we have

$\operatorname*{\mathbb{E}}\limits_{x\sim p}\operatorname{{\rm
logistic}}\left(\frac{\|x\|_{H}}{2E_{1}}\right)\geq\operatorname{{\rm
logistic}}\left(\frac{1}{2}\right)\geq\frac{2}{5}=E_{2}.$

This implies that Definition 8 is satisfied for
$\mathcal{L}^{H}_{\operatorname{{\rm logistic}},k}$ and thus Theorem 10
concludes the statement for
$m\geq\frac{2S}{\varepsilon^{2}}\left(8C^{2}+S\log\frac{2}{\delta}\right)$.

In line with the most compelling scenario, Hilbert space $\mathbb{R}^{d}$,
utilizing the standard inner product as its kernel, we present the following
theorem.

###### Theorem 29

Let $P$ be a probability measure over $\mathbb{R}^{d}$ such that
$P\left(\left\\{x\in\mathcal{X}\colon\|x\|_{H}\geq A\right\\}\right)=0$ and
$S=1+\frac{340(1+kA^{2})}{\sqrt{\max(1,\log(kA^{2}))}}$. There is an
$m=O\left(\frac{S}{\varepsilon^{2}}\left(d\log
S+\log\frac{1}{\delta}\right)\right)$ such that any iid sample
$x_{1},\ldots,x_{m}$ from $P$ with weights $u_{i}=\frac{1}{m}$ provides an
$\varepsilon$-coreset for
$(\mathbb{R}^{d},P,\mathbb{R}^{d},\ell_{\operatorname{{\rm logistic}},k})$
(respectively for
$(\mathcal{X},P,\mathcal{X},\bar{\ell}^{H}_{\operatorname{{\rm logistic}},k})$
) with probability at least $1-\delta$.

Proof  Because of similarity, we only handle the case
$(\mathbb{R}^{d},P,\mathbb{R}^{d},\ell_{\operatorname{{\rm logistic}},k})$.
Given that Lemma 27 asserts the constant function
$s(x)=1+\frac{340(1+kA^{2})}{\sqrt{\max(1,\log(kA^{2}))}}$ as an upper
sensitivity function for $\mathcal{L}_{\operatorname{{\rm logistic}},k}$, we
deduce $\operatorname{\bf Ranges}(\mathcal{T}_{\mathcal{L}_{\operatorname{{\rm
logistic}},k}},\succ)=\operatorname{\bf
Ranges}(\mathcal{L}_{\operatorname{{\rm logistic}},k},\succ)$. To clarify,
every function in $\mathcal{T}_{\mathcal{L}_{\operatorname{{\rm
logistic}},k}}$ is a function in $\mathcal{L}_{\operatorname{{\rm
logistic}},k}$ scaled by a positive constant. This implies ${\rm
VCdim}(\operatorname{\bf Ranges}(\mathcal{T}_{\mathcal{L}_{\operatorname{{\rm
logistic}},k}},\succ))={\rm VCdim}(\operatorname{\bf
Ranges}(\mathcal{L}_{\operatorname{{\rm logistic}},k},\succ)).$ We would like
to remind that

$\mathcal{T}_{{}_{\mathcal{L}_{\operatorname{{\rm
logistic}},k}}}=\left\\{f_{w}(\cdot)=\frac{\operatorname{{\rm
logistic}}(\langle w,\cdot\rangle)+\frac{1}{k}\|w\|_{2}^{2}}{s(\cdot)}\colon
w\in\mathbb{R}^{d}\right\\}.$

For an $f_{w}\in\mathcal{L}_{\operatorname{{\rm logistic}},k}$ and $r\geq 0$,

$\displaystyle\operatorname{\bf range}(f_{w},\succ,r)$
$\displaystyle=\left\\{x\in\mathbb{R}^{d}\colon f_{w}(x)>r\right\\}$
$\displaystyle=\left\\{x\in\mathbb{R}^{d}\colon\operatorname{{\rm
logistic}}(\langle x,w\rangle)+\frac{\|w\|^{2}}{k}>r\right\\}$
$\displaystyle=\left\\{x\in\mathbb{R}^{d}\colon\log\left(1+e^{-\langle
x,w\rangle}\right)>\underbrace{r-\frac{\|w\|^{2}}{k}}_{=t}\right\\}$
$\displaystyle=\left\\{\begin{array}[]{ll}\mathbb{R}^{d}&t\leq 0\\\
\left\\{x\in\mathbb{R}^{d}\colon\langle
x,w\rangle>\log(e^{t}-1)\right\\}&t>0,\end{array}\right.$

which concludes that $\operatorname{\bf
Ranges}(\mathcal{L}_{\operatorname{{\rm logistic}},k},\succ)$ only includes
half-spaces, empty set, and the whole space $\mathbb{R}^{d}$. Therefore, by
Radon’s theorem, ${\rm VCdim}(\operatorname{\bf
Ranges}(\mathcal{L}_{\operatorname{{\rm logistic}},k},\succ))\leq d+1$ (for a
proof, see Lemma 10.3.1 in Matousek 2002). Leveraging Theorem 3, we derive the
statement for $m=O(\frac{S}{\varepsilon^{2}}\left(d\log
S+\log\frac{1}{\delta}\right))$, thereby completing the proof.
In the previous theorem, we assumed that the data is hard-bounded. In the
following results, we try to relax this assumption to a kind of soft bounding
similar to what we have in Theorem 24.

###### Lemma 30

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}^{2}.$ Then

$s(y)=2+\left(2+\frac{\|y\|_{H}}{E_{1}}\right)\frac{680(1+kE_{1}^{2})}{\sqrt{\max(1,\log(2E_{1}^{2}k)}}+\frac{2kE^{2}_{1}+2kE_{1}\|y\|_{H}}{\sqrt{\max(1,\log(2E_{1}^{2}k)}}$

is an upper sensitivity function for
$(\mathcal{X},P,\mathcal{L}^{H}_{\operatorname{{\rm logistic}},k})$ and
$(\mathcal{X},P,\bar{\mathcal{L}}^{H}_{\operatorname{{\rm logistic}},k})$ with
total sensitivity
$S=O\left(\frac{E_{1}^{2}k}{\sqrt{\log(2E_{1}^{2}k)}}\right).$

Proof  As $\operatorname*{\mathbb{E}}_{x\sim P}(\|x\|_{H}^{2})\leq E^{2}_{1}$,
Markov’s inequality implies $\operatorname*{\mathbb{P}}_{x\sim
P}(\|x\|_{H}^{2}\geq 2E^{2}_{1})\leq\frac{1}{2}$. For an arbitrary
$y\in\mathcal{X}$, define
$\mathcal{X}_{y}=\left\\{x\in\mathcal{X}\colon\|x\|_{H}\leq\sqrt{2}E_{1}\max(1,\frac{\|y\|_{H}}{E_{1}})\right\\}$.
Additionally, define

$\mathcal{W}=\left\\{w\in
R^{d}\colon\|w\|_{H}\leq\frac{1}{\sqrt{2}E_{1}}\sqrt{\max(1,\log(2E_{1}^{2}k)}\right\\}.$

Lemma 26 indicates that Lemma 20 is applicable with

$B_{1}=\sqrt{2}E_{1}\max(1,\frac{\|y\|_{H}}{E_{1}}),B_{2}=\frac{1}{\sqrt{2}E_{1}}\sqrt{\max(1,\log(2E_{1}^{2}k)},$
$\displaystyle M_{y}=\phi\left(-B_{1}B_{2}\right)$ $\displaystyle\leq
1+\max(1,\frac{\|y\|_{H}}{E_{1}})\sqrt{\max(1,\log(2E_{1}^{2}k)}$
$\displaystyle\leq\left(2+\frac{\|y\|_{H}}{E_{1}}\right)\sqrt{\max(1,\log(2E_{1}^{2}k)},$

and

$\beta(\alpha)=\beta_{\operatorname{{\rm
logistic}}}(\alpha)=\left\\{\begin{array}[]{cc}\frac{85\alpha^{2}k}{\log(\alpha^{2}k)}&\alpha^{2}k\geq
e\\\ \\\ 84&\alpha^{2}k\leq e.\end{array}\right.$

Consequently,

$\displaystyle\sup_{\|w\|_{H}\leq B_{2}}\frac{\ell^{H}_{{}_{\operatorname{{\rm
logistic}},k}}(y,w)}{\int_{x\in\mathcal{X}}\ell^{H}_{{}_{\operatorname{{\rm
logistic}},k}}(x,w){\rm d}P(x)}$ $\displaystyle=\sup_{\|w\|_{H}\leq
B_{2}}\frac{1}{\int_{x\in\mathcal{X}}\frac{\ell^{H}_{{}_{\operatorname{{\rm
logistic}},k}}(x,w)}{\ell^{H}_{{}_{\operatorname{{\rm logistic}},k}}(y,w)}{\rm
d}P(x)}$ $\displaystyle\leq\sup_{\|w\|_{H}\leq
B_{2}}\frac{1}{\int_{x\in\mathcal{X}_{y}}\frac{\ell^{H}_{{}_{\operatorname{{\rm
logistic}},k}}(x,w)}{\ell^{H}_{{}_{\operatorname{{\rm logistic}},k}}(y,w)}{\rm
d}P(x)}$ (Lemma 20) $\displaystyle\leq\sup_{\|w\|_{H}\leq
B_{2}}\frac{1}{\int_{x\in\mathcal{X}_{y}}\frac{\operatorname{{\rm
logistic}}(0)}{M_{y}\beta(\|x\|_{H})}{\rm d}P(x)}$
$\displaystyle=\frac{M_{y}}{\operatorname{{\rm
logistic}}(0)}\frac{1}{\int_{x\in\mathcal{X}_{y}}\frac{1}{\beta(\|x\|_{H})}{\rm
d}P(x)}$ $\displaystyle(*)\quad$ $\displaystyle\leq
2\left(2+\frac{\|y\|_{H}}{E_{1}}\right)\sqrt{\max(1,\log(2E_{1}^{2}k)}\frac{340(1+kE_{1}^{2})}{\max(1,\log(2kE_{1}^{2}))}.$
$\displaystyle=\left(2+\frac{\|y\|_{H}}{E_{1}}\right)\frac{680(1+kE_{1}^{2})}{\sqrt{\max(1,\log(2E_{1}^{2}k)}}.$

To see ($*$), note that
$M_{y}\leq\left(2+\frac{\|y\|_{H}}{E_{1}}\right)\sqrt{\max(1,\log(2E_{1}^{2}k)}$,
$\operatorname{{\rm logistic}}(2)\geq 0.5$, and

$\displaystyle\int_{x\in\mathcal{X}_{y}}\frac{1}{\beta(\|x\|_{H})}{\rm d}P(x)$
$\displaystyle\geq\int_{\\{x:e\leq k\|x\|_{H}^{2}\leq
2kE^{2}_{1}\\}}\frac{\log(\|x\|_{H}^{2}k)}{85\|x\|^{2}k}{\rm
d}P(x)+\int_{\\{x:k\|x\|_{H}^{2}<e\\}}\frac{1}{85}{\rm d}P(x)$
$\displaystyle\geq\frac{\log(2kE^{2}_{1})}{170kE^{2}_{1}}P\left(\\{x:e\leq
k\|x\|_{H}^{2}\leq
2kE^{2}_{1}\\}\right)+\frac{1}{85}P\left(\\{x:k\|x\|_{H}^{2}<e\\}\right)$
$\displaystyle\geq\frac{\max(1,\log(2kE_{1}^{2}))}{170(1+kE_{1}^{2})}P\left(\\{x:\|x\|_{H}^{2}\leq
2E^{2}_{1}\\}\right)$
$\displaystyle\geq\frac{\max(1,\log(2kE_{1}^{2}))}{340(1+kE_{1}^{2})}.$

Up to this point, our analysis was concentrated on the scenario where
$\|w\|_{H}\leq B_{2}$. Subsequently, we address the case that $\|w\|_{H}\geq
B_{2}=\frac{1}{\sqrt{2}E_{1}}\sqrt{\max(1,\log(2E_{1}^{2}k)}$. Since
$\int_{x\in\mathcal{X}}\ell^{H}_{{}_{\operatorname{{\rm
logistic}},k}}(x,w){\rm d}P(x)\geq\frac{1}{k}\|w\|_{H}^{2}$, we have

$\displaystyle\sup_{\|w\|_{H}\geq B_{2}}\frac{\ell^{H}_{{}_{\operatorname{{\rm
logistic}},k}}(y,w)}{\int_{x\in\mathcal{X}}\ell^{H}_{{}_{\operatorname{{\rm
logistic}},k}}(x,w){\rm d}P(x)}$ $\displaystyle\leq\sup_{\|w\|_{H}\geq
B_{2}}\frac{\frac{1}{k}\|w\|_{H}^{2}+\log(1+e^{-\boldsymbol{K}(y,w)})}{\frac{1}{k}\|w\|_{H}^{2}}$
$\displaystyle\leq\sup_{\|w\|_{H}\geq
B_{2}}\left[1+\frac{k}{\|w\|_{H}^{2}}\log(1+e^{-\boldsymbol{K}(y,w)})\right]$
$\displaystyle\leq\sup_{\|w\|_{H}\geq
B_{2}}\left[1+\frac{k}{\|w\|_{H}^{2}}\log(1+e^{\|y\|_{H}\|w\|_{H}})\right]$
$\displaystyle\leq\sup_{\|w\|_{H}\geq
B_{2}}\left[1+\frac{k}{\|w\|_{H}^{2}}\left(1+\|y\|_{H}\|w\|_{H}\right)\right]$
$\displaystyle\leq 2+\frac{k}{B_{2}^{2}}+\frac{k\|y\|_{H}}{B_{2}}$
$\displaystyle=2+\frac{2kE_{1}^{2}}{\max(1,\log(2E_{1}^{2}k)}+\frac{\sqrt{2}kE_{1}\|y\|_{H}}{\sqrt{\max(1,\log(2E_{1}^{2}k)}}$
$\displaystyle\leq
2+\frac{2kE^{2}_{1}+2kE_{1}\|y\|_{H}}{\sqrt{\max(1,\log(2E_{1}^{2}k)}}.$

Therefore,

$\displaystyle\sup_{w\in\mathcal{X}}\frac{\ell^{H}_{{}_{\operatorname{{\rm
logistic}},k}}(y,w)}{\int_{x\in\mathcal{X}}\ell^{H}_{{}_{\operatorname{{\rm
logistic}},k}}(x,w){\rm d}P(x)}\leq$ $\displaystyle\
\max\Biggl{\\{}\sup_{\|w\|\leq B_{2}}\frac{\ell^{H}_{{}_{\operatorname{{\rm
logistic}},k}}(y,w)}{\int_{x\in\mathcal{X}}\ell^{H}_{{}_{\operatorname{{\rm
logistic}},k}}(x,w){\rm d}P(x)},$ $\displaystyle\qquad\quad\sup_{\|w\|\geq
B_{2}}\frac{\ell^{H}_{{}_{\operatorname{{\rm
logistic}},k}}(y,w)}{\int_{x\in\mathcal{X}}\ell^{H}_{{}_{\operatorname{{\rm
logistic}},k}}(x,w){\rm d}P(x)}\Biggl{\\}}$ $\displaystyle\leq$
$\displaystyle\
\max\left\\{\left(2+\frac{\|y\|_{H}}{E_{1}}\right)\frac{680(1+kE_{1}^{2})}{\sqrt{\max(1,\log(2E_{1}^{2}k)}},\
2+\frac{2kE^{2}_{1}+2kE_{1}\|y\|_{H}}{\sqrt{\max(1,\log(2E_{1}^{2}k)}}\right\\}$
$\displaystyle\leq$ $\displaystyle
2+\left(2+\frac{\|y\|_{H}}{E_{1}}\right)\frac{680(1+kE_{1}^{2})}{\sqrt{\max(1,\log(2E_{1}^{2}k)}}+\frac{2kE^{2}_{1}+2kE_{1}\|y\|_{H}}{\sqrt{\max(1,\log(2E_{1}^{2}k)}}=s(y).$

Consequently, $s(y)$ is an upper sensitivity for $(\mathcal{X},\ P,\
\mathcal{L}^{H}_{\operatorname{{\rm logistic}},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_{y\in\mathcal{X}}s(y){\rm
d}P(y)=O\left(\frac{E_{1}^{2}k}{\sqrt{\max(1,\log(2E_{1}^{2}k)}}\right).$

A similar argument concludes the statement for
$(\mathcal{X},P,\bar{\mathcal{L}}^{H}_{\operatorname{{\rm logistic}},k})$.

###### Theorem 31

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}$,
$P$ is probability measure over $\mathcal{X}$ such that
$\operatorname*{\mathbb{E}}\limits_{x\sim p}\|x\|_{H}^{2}\leq E_{1}$,

$s(x)=2+\left(2+\frac{\|y\|_{H}}{E_{1}}\right)\frac{680(1+kE_{1}^{2})}{\sqrt{\max(1,\log(2E_{1}^{2}k)}}+\frac{2kE^{2}_{1}+2kE_{1}\|y\|_{H}}{\sqrt{\max(1,\log(2E_{1}^{2}k)}},$

and $S=O\left(\frac{E_{1}^{2}k}{\sqrt{\max(1,\log(2E_{1}^{2}k)}}\right)$. 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_{\operatorname{{\rm logistic}},k})$
(respectively for $(\mathcal{X},P,\mathcal{X},\bar{\ell}_{\operatorname{{\rm
logistic}},k})$) with probability at least $1-\delta$, where
$C=(2E_{1}+1)\max(4E_{1}k,2.5)+8E_{1}k+1$.

Proof  Lemma 30 indicates that $s(\cdot)$ and $S$ are an upper sensitivity
function its corresponding total sensitivity for both
$(\mathcal{X},P,\mathcal{L}^{H}_{\operatorname{{\rm logistic}},k})$ and
$(\mathcal{X},P,\bar{\mathcal{L}}^{H}_{\operatorname{{\rm logistic}},k})$.
Note that $\operatorname{{\rm logistic}}(\cdot)$ is decreasing and convex.
using Equation (6), we have

$\operatorname*{\mathbb{E}}\limits_{x\sim p}\operatorname{{\rm
logistic}}\left(\frac{\|x_{i}\|_{H}}{2E_{1}}\right)\geq\operatorname{{\rm
logistic}}\left(\frac{1}{2}\right)\geq\frac{2}{5}=E_{2}.$

Now, the proof follows by applying Theorem 18.
Returning to the scenario where our Hilbert space is $\mathbb{R}^{d}$ equipped
with the standard inner product as its kernel, to utilize Theorem 3, the
computation of ${\rm VCdim}(\operatorname{\bf
Ranges}(\mathcal{T}_{{\mathcal{L}_{\operatorname{{\rm logistic}},k}}},\succ))$
is necessary. The following theorem serves as a valuable instrument for
handling the VC-dimension of linked-range spaces.

For a positive integer $l$, a function
$f:\mathbb{R}^{d}\longrightarrow[0,\infty)$ is called _$l$ -simply
computable_, if the inequality $f(x)>r$ can be verified using $O(d^{l-1})$
steps via simple arithmetic operations $+,-,\times,/$, jumps conditioned on
$>,\ \geq,\ <,\ \leq,\ =,\ \neq$ comparisons on real numbers, and $O(1)$
evaluations of the exponential function $t\rightarrow e^{t}$ on real number
$t$.

######  Theorem 32 (Anthony and Bartlett 2009, Theorem 8.14)

For a family of functions $\mathcal{F}$, if each $f\in\mathcal{F}$ is
$l$-simply computable, then

${\rm VCdim}(\operatorname{\bf Ranges}(\mathcal{F},\succ))=O(d^{l}).$

For each $r\geq 0$,

$\operatorname{\bf range}(w,\succ,r)=\left\\{x\in\mathbb{R}^{d}\colon
f_{w}(x)=\frac{\operatorname{{\rm logistic}}(\langle
w,\cdot\rangle)+\frac{1}{k}\|w\|^{2}}{s(\cdot)}>r\right\\}.$

The inequality $f_{w}(x)>r$ is not simply computable since it contains the
evaluation $\|x\|$ (to compute $s(x)$), which cannot be done by the allowed
operations. To circumvent this issue, we propose a modification to the upper
sensitivity function $s$ outlined in Lemma 30 as follows:

$\displaystyle s(x)$
$\displaystyle=2+\left(2+\frac{\|y\|_{H}}{E_{1}}\right)\frac{680(1+kE_{1}^{2})}{\sqrt{\max(1,\log(2E_{1}^{2}k)}}+\frac{2kE^{2}_{1}+2kE_{1}\|y\|_{H}}{\sqrt{\max(1,\log(2E_{1}^{2}k)}}$
$\displaystyle=2+\left(3+\frac{\|y\|^{2}_{H}}{E^{2}_{1}}\right)\frac{680(1+kE_{1}^{2})}{\sqrt{\max(1,\log(2E_{1}^{2}k)}}+\frac{2kE^{2}_{1}+2k(E_{1}^{2}+\|y\|^{2}_{H})}{\sqrt{\max(1,\log(2E_{1}^{2}k)}}$
$\displaystyle=s_{1}(x).$

Note that $s_{1}$ is also an upper sensitivity function for
$(\mathbb{R}^{d},P,\mathbb{R}^{d},\ell_{\operatorname{{\rm logistic}},k})$
with total sensitivity
$S_{1}=O\left(\frac{E_{1}^{2}k}{\sqrt{\log(E_{1}^{2}k)}}\right).$ Now, if we
work with $s_{1}$ as the upper sensitivity function for
$(\mathbb{R}^{d},P,\mathbb{R}^{d},\ell_{\operatorname{{\rm logistic}},k})$,
then $f_{w}(x)=\frac{\operatorname{{\rm logistic}}(\langle
w,x\rangle)+\frac{1}{k}\|w\|_{2}^{2}}{s_{1}(\cdot)}>r$ is $2$-simply
computable. This is true since

$f_{w}(x)>r\quad\quad\Longleftrightarrow\quad\quad 1+e^{-\langle
w,x\rangle}>\exp\left\\{s_{1}(x)r-\frac{1}{k}\|w\|^{2}\right\\}.$

So, using Theorems 3 and 32, we have the next statement.

###### Theorem 33

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)=2+\left(3+\frac{\|y\|^{2}_{H}}{E^{2}_{1}}\right)\frac{680(1+kE_{1}^{2})}{\sqrt{\max(1,\log(2E_{1}^{2}k)}}+\frac{2kE^{2}_{1}+2k(E_{1}^{2}+\|y\|^{2}_{H})}{\sqrt{\max(1,\log(2E_{1}^{2}k)}},$

and $S=O\left(\frac{E_{1}^{2}k}{\sqrt{\log(E_{1}^{2}k)}}\right).$ There is
$m=O(\frac{2S}{\varepsilon^{2}}\left(d^{2}\log S+\log 1/\delta)\right))$ such
that 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 logistic}},k})$
(respectively for
$(\mathbb{R}^{d},P,\mathbb{R}^{d},\bar{\ell}_{\operatorname{{\rm
logistic}},k})$) with probability at least $1-\delta$.

One might question the necessity of having Theorems 28 and 25 while Theorems
31 and 33 appear stronger and broader. It is crucial to note that in Theorems
31 and 33, the process demands re-sampling using $s$-sensitivity samples,
which relies on evaluating the function $s$. In contrast, Theorems 28 and 25
permit the direct (via uniform sampling) use of given data points since they
were originally sampled from $P$.

###  4.3 Coreset for svm Function

We would like to remind the reader that $\operatorname{{\rm
svm}}(t)=\max(0,1-t)$. The SVM loss, also referred to as Hinge Loss, serves as
a loss function in training classifiers, such as in Support Vector Machines.
Following a similar approach to the one outlined above, we initiate the
process by identifying a function $\beta(\cdot)$ that satisfies the properties
stated in Lemma 20 for $\phi=\operatorname{{\rm svm}}$.

###### Lemma 34

For $\operatorname{{\rm svm}}(x)=\max(0,1-t)$ and $k>0$, we have

$\frac{\operatorname{{\rm svm}}(-\alpha z)+\frac{z^{2}}{k}}{\operatorname{{\rm
svm}}(\alpha z)+\frac{z^{2}}{k}}\leq
1+2\max(1,\alpha^{2}k)\quad\quad\forall\alpha,z\geq 0.$

Proof  For a fixed $\alpha>0$, set $t=\alpha z$, $K=\alpha^{2}k$, and

$\frac{\operatorname{{\rm svm}}(-\alpha z)+\frac{z^{2}}{k}}{\operatorname{{\rm
svm}}(\alpha z)+\frac{z^{2}}{k}}=\frac{\operatorname{{\rm
svm}}(-t)+\frac{t^{2}}{K}}{\operatorname{{\rm
svm}}(t)+\frac{t^{2}}{K}}=f_{K}(t)\quad\quad t\geq 0.$

We can rewrite $f_{K}$ as

$\displaystyle f_{K}(t)$
$\displaystyle=\left\\{\begin{array}[]{ll}\frac{1+t+\frac{t^{2}}{K}}{\frac{t^{2}}{K}}&1\leq
t\\\ \\\ \frac{1+t+\frac{t^{2}}{K}}{1-t+\frac{t^{2}}{K}}&0\leq t\leq
1\end{array}\right.$ (22)
$\displaystyle=\left\\{\begin{array}[]{ll}\frac{K}{t^{2}}+\frac{K}{t}+1&1\leq
t\\\ \\\ 1+\frac{2t}{1-t+\frac{t^{2}}{K}}&0\leq t\leq 1\end{array}\right.$
(26)

One can simply check that $\max_{t\geq 1}f_{K}(t)=1+2K$. Also, if we assume
that $K\geq 1$, then, by simple calculation, we can derive that $\max_{0\leq
t\leq 1}f_{K}(t)=f_{K}(1)=1+2K$. So, using Lemma 19, we obtain

$\sup_{t\geq 0}f_{K}(t)\leq 1+2\max(1,K)\quad\quad\forall K>0.$

Replacing $K$ with $\alpha^{2}z$ concludes the result.

###### Lemma 35

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
$P\left(\left\\{x\in\mathcal{X}\colon\|x\|_{H}\geq A\right\\}\right)=0$. Then
$s(y)=6+4kA^{2}$ is an upper sensitivity function for $(\mathcal{X},\ P,\
\mathcal{L}^{H}_{\operatorname{{\rm svm}},k})$ and $(\mathcal{X},\ P,\
\bar{\mathcal{L}}^{H}_{\operatorname{{\rm svm}},k})$.

Proof  Since $P\left(\left\\{x\in\mathcal{X}\colon\|x\|_{H}\geq
A\right\\}\right)=0$, our computation of $s(y)$ is limited to $\|y\|_{H}\leq
A$. For $w\in\mathcal{W}=\\{w\in\mathcal{X}\colon\|w\|_{H}\leq\frac{1}{A}\\}$,
Lemma 34 indicates that Lemma 20 is applicable with
$B_{1}=A,B_{2}=\frac{1}{A},M=\phi(-1)=2$, and $\beta_{\operatorname{{\rm
svm}}}(\alpha)=1+2\max(1,\alpha^{2}k).$ Using Lemma 21 with
$\gamma(\|x\|_{H})=\frac{\operatorname{{\rm
svm}}(0)}{M\beta_{\operatorname{{\rm
svm}}}(\|x\|_{H})}=\frac{1}{2\beta_{\operatorname{{\rm svm}}}(\|x\|_{H})}$, we
conclude that

$\sup_{\|w\|_{H}\leq\frac{1}{A}}\frac{\ell^{H}_{{}_{\operatorname{{\rm
svm}},k}}(y,w)}{\int_{x\in\mathcal{X}}\ell^{H}_{{}_{\operatorname{{\rm
svm}},k}}(x,w){\rm
d}P(x)}\leq\frac{2}{\int_{\mathcal{X}}\frac{1}{\beta_{\operatorname{{\rm
svm}}}(\|x\|_{H})}{\rm d}P(x)}.$

Note that

$\displaystyle\int_{x\in\mathcal{X}}\frac{1}{\beta_{\operatorname{{\rm
svm}}}(\|x\|_{H})}{\rm d}P(x)$ $\displaystyle\geq\int_{\\{x:1\leq
k\|x\|_{H}^{2}\\}}\frac{1}{1+2k\|x\|_{H}^{2}}{\rm
d}P(x)+\int_{\\{x:k\|x\|^{2}<1\\}}\frac{1}{3}{\rm d}P(x)$
$\displaystyle\geq\frac{1}{1+2kA^{2}}P\left(\left\\{x:\frac{1}{k}\leq\|x\|_{H}^{2}\right\\}\right)+\frac{1}{3}P\left(\left\\{x:\|x\|_{H}^{2}<\frac{1}{k}\right\\}\right)$
$\displaystyle\geq\frac{1}{3+2kA^{2}}.$

This concludes

$\sup_{\|w\|_{H}\leq\sqrt{k}}\frac{\ell^{H}_{{}_{\operatorname{{\rm
svm}},k}}(y,w)}{\int_{x\in\mathcal{X}}\ell^{H}_{{}_{\operatorname{{\rm
svm}},k}}(x,w){\rm d}P(x)}\leq 6+4kA^{2}.$

Since $\int_{x\in\mathbb{R}^{d}}\ell_{{}_{\operatorname{{\rm
svm}},k}}(x,w){\rm d}P\geq\frac{1}{k}\|w\|^{2}$, we have

$\displaystyle\sup_{\|w\|_{H}\geq\frac{1}{A}}\frac{\ell_{{}_{\operatorname{{\rm
svm}},k}}(y,w)}{\int_{x\in\mathcal{X}}\ell_{{}_{\operatorname{{\rm
svm}},k}}(x,w){\rm d}P}$
$\displaystyle\leq\sup_{\|w\|_{H}\geq\frac{1}{A}}\frac{\frac{1}{k}\|w\|_{H}^{2}+\max(0,1-\langle
y,w\rangle_{H})}{\frac{1}{k}\|w\|_{H}^{2}}$
$\displaystyle=\sup_{\|w\|_{H}\geq\frac{1}{A}}\left[1+\frac{k}{\|w\|_{H}^{2}}\max(0,1-\langle
y,w\rangle_{H})\right]$
$\displaystyle\leq\sup_{\|w\|_{H}\geq\frac{1}{A}}\left[1+\frac{k}{\|w\|_{H}^{2}}\max(0,1+\|y\|_{H}\|w\|_{H})\right]$
$\displaystyle\leq\sup_{\|w\|_{H}\geq\frac{1}{A}}\left[1+\frac{k}{\|w\|_{H}^{2}}\left(1+\|y\|_{H}\|w\|_{H}\right)\right]$
$\displaystyle\leq 1+2A^{2}k.$

So, $s(y)=6+4kA^{2}$ is an upper sensitivity function for $(\mathcal{X},\ P,\
\mathcal{L}^{H}_{\operatorname{{\rm svm}},k})$.

###### Theorem 36

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
$P\left(\left\\{x\in\mathcal{X}\colon\|x\|_{H}\geq A\right\\}\right)=0$. For
$S=6+4kA^{2}$, $C=(4A+2)\max(2Ak,1)+8Ak+1$, and
$m=\frac{2S}{\varepsilon^{2}}(8C^{2}+S\log\frac{2}{\delta})$, any iid sample
$x_{1},\ldots,x_{m}$ from $\mathcal{X}$ with weights $u_{i}=\frac{1}{m}$
provides an $\varepsilon$-coreset for
$(\mathcal{X},P,\mathcal{X},\mathcal{L}^{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$.

Proof  Lemma 39 indicates that $s(y)=6+4kA^{2}$ is an upper sensitivity
function. As it is a constant function, $s$-sensitivity sampling is the same
as sampling according to $P$. Notice that $\operatorname{{\rm svm}}$ is convex
and non-increasing. For $E_{1}=A$, using Equation 6, we have

$\operatorname*{\mathbb{E}}\limits_{x\sim p}\operatorname{{\rm
svm}}\left(\frac{\|x_{i}\|_{2}}{2E_{1}}\right)\geq\operatorname{{\rm
svm}}\left(\frac{1}{2}\right)\geq\frac{1}{2}=E_{2}.$

This implies that Definition 8 is satisfied for
$\mathcal{L}^{H}_{\operatorname{{\rm svm}},k}$ and thus Theorem 10 concludes
the statement for
$m\geq\frac{2S}{\varepsilon^{2}}\left(8C^{2}+\log\frac{1}{\delta}\right)$.
Following directly from this theorem, we observe the following corollary.

######  Corollary 37 (Theorem 12, Restated)

Let $\boldsymbol{K}:\mathbb{R}^{d}\times\mathbb{R}^{d}\longrightarrow(0,1]$ be
a reproducing kernel, i.e., a kernel associated with an RKHS, and $P$ be a
probability measure over $\mathbb{R}^{d}$. For $\varepsilon,\delta\in(0,1)$,
there exists a universal constant $C$ (independent of $d$ and
$\boldsymbol{K}$) such that if
$m\geq\frac{C}{\varepsilon^{2}}\log\frac{1}{\delta}$, then, with probability
at least $1-\delta$, for any random sample $X=\\{x_{1},\ldots,x_{m}\\}$ based
on $P$, we have

$\sup_{w\in\mathbb{R}^{d}}|\text{KDE}_{P}(w)-\text{KDE}_{X}(w)|\leq\varepsilon.$

Proof  Note that $\boldsymbol{K}$ and $\phi(t)=\max(0,1-t)$ satisfy Definition
8 with $E_{1}=1$, $E_{2}=\frac{1}{2}$, and

$\ell^{H}_{\phi,k}(x,w)=\phi(\boldsymbol{K}(x,w))+\frac{1}{k}\|w\|_{H}^{2}=1-\boldsymbol{K}(x,w)+\frac{1}{k}\|w\|_{H}^{2}\leq
1-\boldsymbol{K}(x,w)+\frac{1}{k}.$

If set $k=1$, then, with probability at least $1-\delta$, for each
$w\in\mathbb{R}^{d}$, we have

$\displaystyle\left|\int_{x\in\mathbb{R}^{d}}\boldsymbol{K}(x,w){\rm
d}P(x)-\frac{1}{m}\sum_{i=1}^{m}\boldsymbol{K}(x_{i},w)\right|$
$\displaystyle=\left|\int_{x\in\mathbb{R}^{d}}\ell^{H}_{\phi,1}(x,w){\rm
d}P(x)-\frac{1}{m}\sum_{i=1}^{m}\ell^{H}_{\phi,1}(x_{i},w)\right|$ (by Theorem
36)
$\displaystyle\leq\frac{\varepsilon}{2}\int_{x\in\mathbb{R}^{d}}\ell^{H}_{\phi,1}(x,w){\rm
d}P(x)$
$\displaystyle\leq\frac{\varepsilon}{2}\int_{x\in\mathbb{R}^{d}}(2-\boldsymbol{K}(x,w)){\rm
d}P(x)$ (since $\boldsymbol{K}(x,w)\leq 1$) $\displaystyle\leq\varepsilon.$

###### Theorem 38

Let $P$ be a probability measure over $\mathbb{R}^{d}$ such that
$P\left(\left\\{x\in\mathcal{X}\colon\|x\|_{H}\geq A\right\\}\right)=0$ and
$S=6+4kA^{2}$. There exists $m=O\left(\frac{S}{\varepsilon^{2}}(d\log
S+\log\frac{1}{\delta})\right)$ such that any iid sample $x_{1},\ldots,x_{m}$
from $P$ with weights $u_{i}=\frac{1}{m}$ provides an $\varepsilon$-coreset
for $(\mathbb{R}^{d},P,\mathbb{R}^{d},\ell_{\operatorname{{\rm svm}},k})$
(respectively for
$(\mathcal{X},P,\mathcal{X},\bar{\ell}^{H}_{\operatorname{{\rm svm}},k})$with
probability at least $1-\delta$.

Proof  Given that Lemma 39 asserts the constant function
$s(x)=3+2kA^{2}+\sqrt{k}A$ as an upper sensitivity function for
$\mathcal{L}_{\operatorname{{\rm svm}},k}$, we deduce $\operatorname{\bf
Ranges}(\mathcal{T}_{\mathcal{L}_{\operatorname{{\rm
svm}},k}},\succ)=\operatorname{\bf Ranges}(\mathcal{L}_{\operatorname{{\rm
svm}},k},\succ)$. Notice $\operatorname{\bf
Ranges}(\mathcal{T}_{\mathcal{L}_{\operatorname{{\rm
svm}},k}},\succ)=\operatorname{\bf Ranges}(\mathcal{L}_{\operatorname{{\rm
svm}},k},\succ)$ since each function in
$\mathcal{T}_{\mathcal{L}_{\operatorname{{\rm svm}},k}}$ is a function in
$\mathcal{L}_{\operatorname{{\rm svm}},k}$ scaled by a positive constant. For
an $f_{w}\in\mathcal{L}_{\operatorname{{\rm svm}},k}$ and $r\geq 0$,

$\displaystyle\operatorname{\bf range}(f_{w},\succ,r)$
$\displaystyle=\left\\{x\in\mathbb{R}^{d}\colon f_{w}(x)>r\right\\}$
$\displaystyle=\left\\{x\in\mathbb{R}^{d}\colon\max(0,1-\langle
x,w\rangle)+\frac{\|w\|^{2}}{K}>r\right\\}$
$\displaystyle=\left\\{x\in\mathbb{R}^{d}\colon\max(0,1-\langle
x,w\rangle)>\underbrace{r-\frac{\|w\|^{2}}{K}}_{=t}\right\\}$
$\displaystyle=\left\\{\begin{array}[]{ll}\mathbb{R}^{d}&t<0\\\ \\\
\left\\{x\in\mathbb{R}^{d}\colon\langle x,w\rangle<1-t\right\\}&t\geq
0,\end{array}\right.$

which concludes that $\operatorname{\bf
Ranges}(\mathcal{L}_{\operatorname{{\rm svm}},k},\succ)$ only includes half-
spaces and the whole space $\mathbb{R}^{d}$. Therefore, by Radon’s theorem,
${\rm VCdim}(\operatorname{\bf Ranges}(\mathcal{L}_{\operatorname{{\rm
svm}},k},\succ))\leq d+1$ (for a proof, see Lemma 10.3.1 in (Matousek, 2002)).
Using Theorem 3, we also have the statement of Theorem 28 for $m\geq
O(\frac{S}{\varepsilon^{2}}\left(d\log S+\log\frac{1}{\delta}\right))$,
completing the proof. A similar argument establishes the result for
$(\mathcal{X},P,\bar{\mathcal{L}}^{H}_{\operatorname{{\rm svm}},k})$.

Continuing in line with prior sections, we aim to establish a theorem that
addresses-soft bounding on data instead of employing a hard boundary. In the
subsequent discussion, we substantiate such a result.

###### Lemma 39

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}}_{x\sim p}\|x\|_{H}\leq E_{1}^{2}$. Then
$s(x)=(6+8kE_{1}^{2})\left(2+\frac{\|y\|_{H}}{E_{1}}\right)$ is an upper
sensitivity function for $(\mathcal{X},P,\mathcal{L}^{H}_{\operatorname{{\rm
svm}},k})$ and $(\mathcal{X},P,\bar{\mathcal{L}}^{H}_{\operatorname{{\rm
svm}},k})$ with total sensitivity at most $18+24kE_{1}^{2}$.

Proof  As $\operatorname*{\mathbb{E}}_{x\sim P}(\|x\|_{H}^{2})\leq E^{2}_{1}$,
Markov’s inequality implies $\operatorname*{\mathbb{P}}_{x\sim
P}(\|x\|_{H}^{2}\geq 2E^{2}_{1})\leq\frac{1}{2}$. For an arbitrary
$y\in\mathcal{X}$, define
$\mathcal{X}_{y}=\left\\{x\in\mathcal{X}\colon\|x\|_{H}\leq\sqrt{2}\max(E_{1},\|y\|_{H})\right\\}$.
Additionally, define
$\mathcal{W}=\\{w\in\mathcal{X}\colon\|w\|_{H}\leq\frac{1}{\sqrt{2}E_{1}}\\}$.
Lemma 26 indicates that Lemma 20 is applicable with
$B_{1}=\sqrt{2}\max(E_{1},\|y\|_{H})$, $B_{2}=\frac{1}{\sqrt{2}E_{1}}$,
$\operatorname{{\rm
svm}}(-B_{1}B_{2})=1+\max\left(1,\frac{\|y\|_{H}}{E_{1}}\right)\leq
2+\frac{\|y\|_{H}}{E_{1}}=M_{y}$, and

$\beta(\alpha)=\beta_{\operatorname{{\rm
svm}}}(\alpha)=1+2\max(1,\alpha^{2}k).$

Consequently,

$\displaystyle\sup_{\|w\|_{H}\leq B_{2}}\frac{\ell^{H}_{{}_{\operatorname{{\rm
svm}},k}}(y,w)}{\int_{x\in\mathcal{X}}\ell^{H}_{{}_{\operatorname{{\rm
svm}},k}}(x,w){\rm d}P(x)}$ $\displaystyle=\sup_{\|w\|_{H}\leq
B_{2}}\frac{1}{\int_{x\in\mathcal{X}}\frac{\ell^{H}_{{}_{\operatorname{{\rm
svm}},k}}(x,w)}{\ell^{H}_{{}_{\operatorname{{\rm svm}},k}}(y,w)}{\rm d}P(x)}$
$\displaystyle\leq\sup_{\|w\|_{H}\leq
B_{2}}\frac{1}{\int_{x\in\mathcal{X}_{y}}\frac{\ell^{H}_{{}_{\operatorname{{\rm
svm}},k}}(x,w)}{\ell^{H}_{{}_{\operatorname{{\rm svm}},k}}(y,w)}{\rm d}P(x)}$
(Lemma 20) $\displaystyle\leq\sup_{\|w\|_{H}\leq
B_{2}}\frac{1}{\int_{x\in\mathcal{X}}\frac{\operatorname{{\rm
svm}}(0)}{M_{y}\beta(\|x\|_{H})}{\rm d}P(x)}$
$\displaystyle=\frac{M_{y}}{\int_{x\in\mathcal{X}_{y}}\frac{1}{\beta(\|x\|_{H})}{\rm
d}P(x)}$
$\displaystyle\leq\frac{2+\frac{\|y\|_{H}}{E_{1}}}{\int_{x\in\mathcal{X}_{y}}\frac{1}{\beta(\|x\|_{H})}{\rm
d}P(x)}$ $\displaystyle(*)\quad$
$\displaystyle\leq(6+8kE_{1}^{2})\left(2+\frac{\|y\|_{H}}{E_{1}}\right).$

To see ($*$), note that

$\displaystyle\int_{x\in\mathcal{X}_{y}}\frac{1}{\beta(\|x\|_{H})}{\rm d}P$
$\displaystyle\geq\int_{\\{x:1\leq k\|x\|_{H}^{2}\leq
2kE^{2}_{1}\\}}\frac{1}{1+2k\|x\|_{H}^{2}}{\rm
d}P+\int_{\\{x:k\|x\|_{H}^{2}<1\\}}\frac{1}{3}{\rm d}P$
$\displaystyle\geq\frac{1}{1+4kE_{1}^{2}}P\left(\\{x:1\leq k\|x\|_{H}^{2}\leq
2kE^{2}_{1}\\}\right)+\frac{1}{3}P\left(\\{x:k\|x\|_{H}^{2}<1\\}\right)$
$\displaystyle\geq\min\left(\frac{1}{1+4kE_{1}^{2}},\frac{1}{3}\right)P\left(\\{x:\|x\|_{H}^{2}\leq
2E^{2}_{1}\\}\right)$ $\displaystyle\geq\frac{1}{6+8kE_{1}^{2}}.$

As we have only considered the case that $\|w\|_{H}\leq B_{2}$, to complete
the proof, we should work with $\|w\|_{H}\geq B_{2}$ as well. Since
$\int_{x\in\mathcal{X}}\ell^{H}_{{}_{\operatorname{{\rm svm}},k}}(x,w){\rm
d}P\geq\frac{1}{k}\|w\|_{H}^{2}$, we have

$\displaystyle\sup_{\|w\|_{H}\geq B_{2}}\frac{\ell^{H}_{{}_{\operatorname{{\rm
svm}},k}}(y,w)}{\int_{x\in\mathcal{X}}\ell^{H}_{{}_{\operatorname{{\rm
svm}},k}}(x,w){\rm d}P}$ $\displaystyle\leq\sup_{\|w\|_{H}\geq
B_{2}}\frac{\frac{1}{k}\|w\|_{H}^{2}+\max(0,1-\langle
y,w\rangle_{H})}{\frac{1}{k}\|w\|_{H}^{2}}$
$\displaystyle\leq\sup_{\|w\|_{H}\geq
B_{2}}\left[1+\frac{k}{\|w\|_{H}^{2}}\max(0,1-\langle y,w\rangle_{H})\right]$
$\displaystyle\leq\sup_{\|w\|_{H}\geq
B_{2}}\left[1+\frac{k}{\|w\|_{H}^{2}}\max(0,1+\|y\|_{H}\|w\|_{H})\right]$
$\displaystyle=\sup_{\|w\|_{H}\geq
B_{2}}\left[1+\frac{k}{\|w\|_{H}^{2}}\left(1+\|y\|_{H}\|w\|_{H}\right)\right]$
$\displaystyle\leq 1+2kE_{1}^{2}+\sqrt{2}kE_{1}\|y\|_{H}.$

Therefore,

$\displaystyle\sup_{w\in\mathcal{X}}\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}\leq$
$\displaystyle\max\Biggl{\\{}\sup_{\|w\|\leq\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},$