# Anisotropic response of spin susceptibility in the superconducting state of
UTe2 probed with 125Te-NMR measurement

Genki Nakamine  Department of Physics, Kyoto University, Kyoto 606-8502, Japan
Katsuki Kinjo  Department of Physics, Kyoto University, Kyoto 606-8502, Japan
Shunsaku Kitagawa  Department of Physics, Kyoto University, Kyoto 606-8502,
Japan Kenji Ishida  Department of Physics, Kyoto University, Kyoto 606-8502,
Japan Yo Tokunaga  ASRC, Japan Atomic Energy Agency, Tokai, Ibaraki 319-1195,
Japan Hironori Sakai  ASRC, Japan Atomic Energy Agency, Tokai, Ibaraki
319-1195, Japan Shinsaku Kambe  ASRC, Japan Atomic Energy Agency, Tokai,
Ibaraki 319-1195, Japan Ai Nakamura  IMR, Tohoku University, Oarai, Ibaraki
311-1313, Japan Yusei Shimizu  IMR, Tohoku University, Oarai, Ibaraki
311-1313, Japan Yoshiya Homma  IMR, Tohoku University, Oarai, Ibaraki
311-1313, Japan Dexin Li  IMR, Tohoku University, Oarai, Ibaraki 311-1313,
Japan Fuminori Honda  IMR, Tohoku University, Oarai, Ibaraki 311-1313, Japan
Dai Aoki  IMR, Tohoku University, Oarai, Ibaraki 311-1313, Japan University
Grenoble, CEA, IRIG-PHERIQS, F-38000 Grenoble, France

###### Abstract

To investigate spin susceptibility in a superconducting (SC) state, we
measured the 125Te-nuclear magnetic resonance (NMR) Knight shifts at magnetic
fields ($H$) up to 6.5 T along the $b$ and $c$ axes of single-crystal UTe2, a
promising candidate for a spin-triplet superconductor. In the SC state, the
Knight shifts along the $b$ and $c$ axes ($K_{b}$ and $K_{c}$, respectively)
decreased slightly and the decrease in $K_{b}$ was almost constant up to 6.5
T. The reduction in $K_{c}$ decreased with increasing $H$, and $K_{c}$ was
unchanged through the SC transition temperature at 5.5 T, excluding the
possibility of spin-singlet pairing. Our results indicate that spin
susceptibilities along the $b$ and $c$ axes slightly decrease in the SC state
in low $H$, and the $H$ response of SC spin susceptibility is anisotropic in
the $bc$ plane. We discuss the possible $d$-vector state within the spin-
triplet scenario and suggest that the dominant $d$-vector component for the
case of $H\parallel b$ changes above 13 T, where $T_{\rm c}$ increases with
increasing $H$.

††preprint: APS/123-QED

Newly discovered UTe2 with an orthorhombic structure has attracted increasing
attention owing to its unusual superconducting (SC) properties[1, 2]. It can
exhibit superconductivity at magnetic fields ($H$) that are much higher than
the Pauli-limiting field, which can be calculated from the SC transition
temperature $T_{\rm c}$, and $H$-boosted superconductivity appears when
$H\parallel b$[1, 3]. A novel re-entrant superconductivity was also reported
for a case when $H$ was applied at a certain angle to the $bc$ plane[4].
Although no ferromagnetic ordering was observed near the SC phase in UTe2,
such robustness of superconductivity against $H$ seems to be a common feature
in uranium-based ferromagnetic and nearly ferromagnetic superconductors[5]. In
addition, pressure measurements revealed multiple SC phases[6, 7, 8, 9], which
can be tuned by $H$[10, 9], and a presumably magnetic ordered phase above 1.8
GPa[8, 11, 9]. Furthermore, spontaneously broken time-reversal symmetry, as
revealed from the Kerr measurement,[12] and the presence of the chiral
Majorana edge and surface state, as observed using scanning tunneling
spectroscopy,[13] were suggested. UTe2 is like a “toy box” for condensed
matter physicists as it storages most of fascinating topics at present.

In a previous study[1], we reported that UTe2 is classified as an
unconventional superconductor because of the absence of a coherence peak just
below $T_{\rm c}$; moreover, the small decrease in the Knight shift when
$H\parallel b$, which is much smaller than the expected decrease in a spin-
singlet superconductor, is favorable for a spin-triplet scenario, because the
large spin component remains in the SC state. Similar Knight-shift behaviors
were also observed in UPt3[15, 16] and UCoGe[17, 18]. To ensure spin triplet
superconductivity, it is important to identify the spin state of the SC state.
For this purpose, UTe2 is one of the most suitable superconductors to study
physical properties of spin-triplet pairing because superconductivity emerges
from the paramagnetic state without the effect from the ordered state.

Spin-triplet superconductivity possesses spin degrees of freedom, which can be
expressed as the $d$ vectors perpendicular to the spin components of the spin-
triplet pairing[19]. If the $d$ vector is fixed to one of the crystalline axes
by some mechanism, the spin part of the Knight shift decreases in the SC state
when the magnetic field $H$ is parallel to the $d$ vector
($\mbox{\boldmath$H$}\parallel\mbox{\boldmath$d$}$); however, it remains
unchanged in the case of $\mbox{\boldmath$H$}\perp\mbox{\boldmath$d$}$. The
$d$-vector component can be derived from the measurements of the Knight shift
along each crystalline axis. In the previous study, we performed NMR
measurements in $H\parallel b$ on the single-crystal sample prepared using a
natural tellurium source with 7.1% 125Te, which is a nuclear magnetic
resonance (NMR)-active isotope. To identify the spin state thoroughly, NMR
measurements when $H\parallel c$ and $H\parallel a$ are needed. However, the
NMR intensity when $H\parallel c$ was not sufficient to obtain reliable
results as the NMR spectrum in $H\parallel c$ is broader than that in
$H\parallel b$. This is because of the larger spin susceptibility in the $c$
axis than that in the $b$ axis at low temperatures. Thus, in the present
study, we used a 125Te-enriched single-crystal sample that contained 99.9% of
125Te. This ensured more reliable NMR measurements because the signal
intensity of the present sample was roughly one order of magnitude larger than
that of the previous sample.

Herein, we report the $H$ dependence of the Knight shift in the SC state along
the $b$ and $c$ axes, since the NMR spectrum when $H\parallel a$ could not be
observed below 20 K due to the divergence of the nuclear spin-spin relaxation
rate $1/T_{2}$[2]. The findings by the present measurements support the
existence of spin-triplet pairing and reveal that the $d$-vector includes the
$\hat{b}$ and $\hat{c}$ components that show an anisotropic response against
$H$ in the $bc$ plane.

Figure 1: (A) Image of the crystal structure of UTe2 prepared with the program
VESTA[21]. (B) Upper critical field $H_{\rm{c2}}$ for a magnetic field applied
along the $b$ (diamonds) and $c$ (circles) axes. The solid circles denote
$T_{\rm c}$ of the 125Te-enriched sample, which is consistent with previous
results[2, 3]. The dotted line indicates the $d$-vector pinning field $H_{\rm
pin}$ for $H\parallel b$ estimated from the decrease in $K_{b}$ and $A_{{\rm
hf},b}$. (C, D) 125Te NMR spectra measured when (C)$H\parallel b$ and
(D)$H\parallel c$, respectively. The dotted peaks show signals from the Te(1)
and Te(2) sites, which are simulated with the resonance frequencies estimated
from the angle dependence of the spectrum shown in the supplemental
material[22].

Single-crystal UTe2 was grown using the chemical transport method with iodine
as the transport agent. Natural uranium and 125 Te-enriched metals were used
as starting materials for the present sample. The 125Te ($I$ = 1/2,
gyromagnetic ratio ${}^{125}\gamma_{n}$/2$\pi$ = 13.454 MHz/T)-NMR
measurements were performed on a single crystal of size
3.5$\times$0.7$\times$1.4 mm3. The frequency-swept NMR spectrum was obtained
using the Fourier transform of a spin-echo signal observed after the spin-echo
RF pulse sequence with a 3 kHz step in a fixed magnetic field. The magnetic
field was calibrated using the 65Cu (${}^{65}\gamma$/2$\pi$ = 12.089 MHz/T)
NMR signal from the NMR coil. The NMR spectrum in the SC state was recorded
with the field-cooling process. We used the split SC magnet, which generated a
horizontal field, and combined it with a single-axis rotator to apply a
magnetic field exactly parallel to the $b$ or $c$ axis; the $a$-axis was the
rotation axis. Low-temperature NMR measurements down to 70 mK were performed
using a 3He-4He dilution refrigerator, and the single-crystalline sample was
immersed into the mixture. The AC susceptibility was measured by recording the
resonance frequency of the NMR-tank circuit during cooling to determine the
$T_{\rm c}$ value of the sample under $H$.

UTe2 exhibits two crystallographically inequivalent Te sites, 4$j$ and 4$h$,
with point symmetries $mm$2 and $m$2$m$, respectively. We denote these sites
as Te(1) and Te(2), respectively, as shown in Fig. 1 (A). The $T_{\rm c}$ of
the present sample determined by the AC susceptibility measurement was
consistent with the previous results, as shown in Fig. 1 (B)[2, 3]. Figures 1
(C) and (D) show the frequency-swept NMR spectrum measured at 3 T when
$H\parallel b$ (C) and $H\parallel c$ (D), respectively. The Te(1) and Te(2)
signals were distinct when $H\parallel b$ but overlapped when $H\parallel c$.
Thus, the Te(2) signal was recorded when $H\parallel b$, and the broad peak
consisting of the Te(1) and Te(2) signals was recorded when $H\parallel c$ for
the Knight shift and linewidth measurements. The Knight shift at the Te(2)
site was determined from the spectral-peak frequency because the contribution
of the Te(2) site was dominant even in the broad spectrum when $H\parallel c$.

Figure 2: NMR spectra at several temperatures at 3 T along the $b$ (A) and $c$
(B) axes. NMR spectra at 5.5 T along the $c$ axis (C). The dotted line in each
figure represents the normal-state peak position.

Figures 2 (A) and (B) indicate the NMR spectra measured at several
temperatures at 3 T in $H\parallel b$ (A) and $H\parallel c$ (B),
respectively, which are shown against $K\equiv$ ($f-f_{0}$) / $f_{0}$. Here,
$f$ is the NMR frequency, and $f_{0}$ is the reference frequency determined as
$f_{0}=(\gamma_{n}/2\pi)H$. Both spectra widen from just below $T_{\rm c}$ as
shown in the supplemental material[22], which ensures that the NMR spectrum in
the SC state was measured. In addition, shoulder peaks appear in the
$H\parallel b$ spectrum below 0.9 K. Because this may suggest the presence of
multiple SC phases in $H$, the origin of the shoulder peaks must be thoroughly
investigated. In this study, we focus on the temperature variation of the
central peak, and the details of the shoulder peaks will be summarized in a
separate study. Notably, the main peak of the $H\parallel b$ spectrum,
depicted with an arrow, shifts in the SC state, which is visible as a shift
from the dotted line showing the normal-state Knight shift. In contrast, the
peak of the $H\parallel c$ spectrum, shown by an arrow, slightly shifts in the
SC state at 3 T [Fig. 2 (B)]; however, the shift of the peak could not be
recognized in the $H\parallel c$ spectrum measured at 5.5 T, although the
broadening of the spectrum was observed in the SC state [Fig. 2 (C)].
Subsequently, $K_{i}$ ($i$ = $b$ and $c$) is determined by the peak
frequencies shown by the arrows.

Figure 3:  Temperature dependence of $\Delta K_{b}$ (A) and $\Delta K_{c}$ (B)
measured at 1, 3, and 5.5 T (see in the text). Dashed lines are added as a
guide to the eye. Temperature dependence of the AC susceptibility $\chi$ at
the same magnetic fields along the $b$ (C) and $c$ (D) axes. The errors of the
NMR Knight shift are determined from the resolution of FT signals.

We investigated the temperature variation of $K_{b}$ and $K_{c}$ measured at
several magnetic fields below 5.5 T. Figures 3 (A) and (B) represent the
temperature variation of $\Delta K_{b}(T)$ (A) and $\Delta K_{c}(T)$ (B) at
$\mu_{0}H$ = 1, 3, and 5.5 T, which are compared with the temperature
dependence of the AC susceptibility. Here, $\Delta K_{i}(T)$ ($i$ = $b$ and
$c$) is defined as $\Delta K_{i}(T)\equiv K_{i}(T)-K_{n,i}$ with the normal-
state Knight shift denoted as $K_{n,i}$. The decrease in $\Delta K_{b}(T)$
observed at 1 T is $\sim$ 0.1%, which is consistent with the previous
result[1] and the recent theoretical calculation based on the spin-triplet
state[23]. Further reductions at a low temperature, related to the multi-gap
properties, were not observed in the present sample as well as in the previous
sample. Notably, the decrease observed at 1 T is almost the same in $\Delta
K_{b}$ and $\Delta K_{c}$. The decreases in $\Delta K_{b}(T)$ at 3 and 5.5 T
in the SC state, which are slightly smaller than that at 1 T, appear to be
inconsistent with the previous result[1]. This could be due to the fitting of
the whole spectrum for the estimation of the Knight shift in the previous
measurement on the 125Te natural-abundant sample. The decrease in $\Delta
K_{b}$ in the SC state seems to be almost $H$-independent above 3 T. In
contrast, $\Delta K_{c}$ at the lowest temperatures became zero with an
increase in $H$, as shown in Fig. 3 (B).

Figure 4:  The magnetic field dependence of the decrease in $\Delta K_{b}$
(diamonds) and $\Delta K_{c}$ (circles). The solid and dashed lines represent
the calculated SC diamagnetic shielding effects $\Delta K_{{\rm dia},b}$ and
$\Delta K_{{\rm dia},c}$, respectively. The inset shows the $H$ dependence of
the decrease in $K_{{\rm spin},i}$ ($\Delta K_{{\rm spin},i}$) estimated by
subtracting $\Delta K_{{\rm dia},i}$ from $\Delta K_{i}$.

To observe the $H$ dependence of the $K_{i}$ decrease in the SC state more
quantitatively, $\Delta K_{i}$ at the lowest temperature ($\sim 0.1$ K),
$\Delta K_{i}(\sim 0.1{\rm K})$ is plotted against $H$ in Fig. 4. In general,
$\Delta K_{i}$ is attributed to two contributions: a decrease in the spin part
of $K_{i}$ ($\Delta K_{{\rm spin,}i}$) in the SC state and the SC diamagnetic
shielding effect $\Delta K_{{\rm dia},i}$, which is expressed as [24]

$\Delta K_{{\rm dia},i}=\frac{H_{c1,i}}{H}\frac{\ln(\frac{\beta
d}{\sqrt{e}\xi})}{\ln{\kappa}}.$ (1)

Here, $\xi$ is the GL coherence length; $\beta$ is a factor depending on the
vortex structure and is 0.38 for the triangular vortex lattice, and $d$ is the
distance between vortices and is calculated using the relation
$\phi_{0}=\frac{\sqrt{3}}{2}d^{2}(\mu_{0}H).$ We estimate the $H$ dependence
of $\Delta K_{{\rm dia},i}$ ($i$ = $b$ and $c$) as follows: In the estimation
of $\Delta K_{{\rm dia},c}$, we use the SC critical field ($H_{c}$) of UTe2,
which is reported to be 49 mT[25], and the upper critical field
($H_{\rm{c2}}$) along the $c$ axis, which is $\sim 11$ T, as shown in Fig. 1
(B). This gives $\mu_{0}H_{{c1},c}$ = 1.2 mT, $\xi$ = 5.38 nm, and $\kappa$ =
159, and the $H$ dependence of $\Delta K_{{\rm dia},c}$ is shown by the dashed
curve in Fig. 4. For the estimation of $\Delta K_{{\rm dia},b}$, we refer to
$\mu_{0}H_{c1}$ = 2 mT[25], and $H_{\rm{c2}}$ along the $b$ axis is assumed to
be $\sim$ 17 T from the extrapolation of $H$ dependence of $T_{\rm c}$ in the
low-$H$ region. The $H$ dependence of $\Delta K_{{\rm dia},b}$ is indicated by
the solid curve in Fig. 4. As highlighted by Paulsen et al., the $H_{\rm c1}$
value along the $b$ axis is unexpectedly large and is two times the estimated
value from $H_{c}$[25]. Even if such an unexpectedly large $H_{c1}$ is adopted
for $H\parallel b$, the observed $H$ dependence of the $K_{b}$ decrease cannot
be explained solely based on the $H$ dependence of $\Delta K_{{\rm dia},b}$;
however, it indicates that $K_{\rm spin}$ along the $b$ and $c$ axes decreases
in the SC state, and the decrease in $K_{\rm spin}$ shows an anisotropic
response against applied $H$, as shown in the inset of Fig. 4. This suggests
that the decrease in the spin susceptibility is maintained at least up to 6.5
T when $H\parallel b$; in contrast, it gradually becomes small when
$H\parallel c$, and the spin susceptibility remains unchanged with temperature
at 5.5 T.

Table 1: Classification of odd-parity SC order parameters for point groups with $D_{2h}$.[26] Irreducible representation | Basis function
---|---
$A_{u}$ |  $k_{a}$$\hat{a}$, $k_{b}$$\hat{b}$, $k_{c}$$\hat{c}$
$B_{1u}$ |  $k_{b}$$\hat{a}$, $k_{a}$$\hat{b}$
$B_{2u}$ |  $k_{a}$$\hat{c}$, $k_{c}$$\hat{a}$
$B_{3u}$ |  $k_{c}$$\hat{b}$, $k_{b}$$\hat{c}$

We discuss the plausible SC state based on the present experimental results.
As mentioned in the introduction, the SC pairing in UTe2, at least at ambient
pressure, has been considered to be a spin-triplet state. $K_{c}$ remains
unchanged with temperature in the SC state at 5.5 T; this excludes the
possibility of spin-singlet pairing even though vortex and/or the $H$-induced
quasiparticle contribution is considered. This is because the decrease in the
spin susceptibility should be observed in all directions for spin-singlet
pairing. This further supports the spin-triplet scenario. With regard to the
spin-triplet superconductivity with odd parity, the possible SC order
parameters were highlighted from an ordinary classification theory with
$D_{2h}$ point group symmetry, which are shown in TABLE 1[26]. Since no
indication of non-unitary states was observed just below $T_{\rm c}$ in our
measurements, non-unitary states are not considered below. The spin
susceptibility decreases with a similar magnitude for $H\parallel b$ and
$H\parallel c$ in low $H$; this suggests that the $d$-vector contains finite
$\hat{b}$ and $\hat{c}$ components in low $H$. If the strong Ising anisotropy
along the $a$ axis in the normal-state spin susceptibility is considered, the
$d$ vector is expected to be perpendicular to the $a$ axis; thus, the $B_{3u}$
state is a promising candidate. This seems to be consistent with the point-
node gap suggested by angle-resolved specific-heat measurements[27]. However,
because the relationship between the normal-state spin and the $d$-vector
anisotropy is not clear at present, the $A_{u}$ state might also be possible.
In this case, the component of each basis is highly anisotropic in the $k$
space. To distinguish the two possibilities, the Knight shift measurement
along the $a$ axis would provide important information regarding the $\hat{a}$
component, if it can be measured.

Furthermore, the anisotropic response of the SC spin susceptibility in the
$bc$ plane against the applied $H$ suggests that the $\hat{c}$ component in
the $d$-vector becomes small when $H\parallel c$ and is nearly zero at 5.5 T;
moreover, the $\hat{b}$ component is robust for $H\parallel b$, thus
indicating that the $d$-vector is strongly pinned along the $b$ axis. Thus, we
consider that the characteristic feature of the low-$H$ SC state is the
suppression of the spin-susceptibility in $H\parallel b$ (the presence of a
finite $\hat{b}$ component in the $d$ vector). If so, this SC state can
sustain up to $H_{\rm pin}$ and a new SC state sets in above $H_{\rm pin}$,
where the $\bm{d}$ vector is perpendicular to the $b$ axis and $\Delta
K_{b}=0$. The value of $H_{\rm pin}$ can be estimated from the balance between
the SC condensation energy of the low-$H$ superconductivity
($\mu_{0}H_{c}^{2}/2$) and the Zeeman energy at $H_{\rm pin}$
($\frac{1}{2}\mu_{0}\Delta\chi_{b}H_{\rm pin}^{2}$). Similar discussion was
also done for the ferromagnetic superconductor UCoGe[28]. $H_{\rm pin}$ is
estimated to be $\sim 13$ T from the decrease in spin susceptibility along the
$b$ axis $\Delta\chi_{b}$ derived from the relation $\Delta\chi_{b}=\Delta
K_{{\rm spin},b}/A_{{\rm hf},b}$ with $\Delta K_{{\rm spin},b}\sim 0.060$%.
Here, $A_{{\rm hf},b}$ is a hyperfine coupling constant along the $b$ axis,
which was reported as $A_{{\rm hf},b}=5.18$ (T /$\mu_{B}$) from the $K$ \-
$\chi$ plot in the normal state[2]. Notably, this $H_{\rm pin}$ is close to
the critical field of $H_{\rm{c2}}$, at which $T_{\rm c}$ is minimum in $H$
and increases with $H$, as shown in Fig. 1 (B). The $H$-boosted
superconductivity might be interpreted as a different SC state where the $d$
vector can rotate away from the $b$ axis.

Recently, Ishizuka and Yanase calculated the maximum magnitude of
intrasublattice $d$-vector components in the whole momentum space. They showed
that the predominant $d$-vector components for the $B_{3u}$ and $A_{u}$ are
$k_{b}\hat{c}$ and $k_{b}\hat{b}$, respectively, and these two states are
almost degenerate[29]. Thus, one interesting scenario to interpret the
anomalous $H_{\rm{c2}}$ behavior in $H\parallel b$ is that the low-$H$
(high-$H$) superconductivity corresponds to the $A_{u}$ ($B_{3u}$) state, and
the $d$-vector rotation occurs at approximately 13 T. To verify this case,
Knight shift measurement above 13 T in $H\parallel b$ is also crucial, and we
expect the $K_{b}$ decrease to become smaller above 13 T and the $K_{b}$ to
remain unchanged in the high-$H$ SC state.

In conclusion, we performed 125Te-NMR on a single crystal of 125Te-enriched
UTe2 and measured the NMR Knight shift when $H\parallel b$ and $H\parallel c$
below $T_{\rm c}$. A slight decrease was observed in both $K_{b}$ and $K_{c}$
at low $H$; however, $K_{c}$ remained unchanged at 5.5 T between the SC and
normal state. The latter further supports the spin-triplet scenario, and the
former indicates the finite components of $\hat{b}$ and $\hat{c}$ in the SC
$d$ vector. From the detailed $H$ dependence, although the $\hat{c}$ component
is gradually suppressed when $H\parallel c$, the $\hat{b}$ component is finite
at least up to 6.5 T, indicating that the $d$ vector is pinned along the $b$
axis. From the estimation of the pinning field $H_{\rm pin}$, we suggest that
the SC character would be different between the low-$H$ and high-$H$ SC
phases, particularly about the dominant $d$-vector direction. Further
experiments to identify the spin state in the high-$H$ SC state, and to
clarify the origin of the shoulder peaks in $H\parallel b$ are needed, and now
in progress.

###### Acknowledgements.

The authors would like to thank M. Manago, J. Ishizuka, Y. Yanase, Y. Maeno,
S. Yonezawa, and J-P. Brison, G. Knebel, and J. Flouquet for valuable
discussions. This work was supported by the Kyoto University LTM Center,
Grants-in-Aid for Scientific Research (Grant Nos. JP15H05745, JP17K14339,
JP19K03726, JP16KK0106, JP19K14657, JP19H04696, JP19H00646, and JP20H00130)
and Grant-in-Aid for JSPS Research Fellows (Grant No. JP20J11939) from JSPS.

## References

  * Ran  _et al._ [2019a] S. Ran, C. Eckberg, Q.-P. Ding, Y. Furukawa, T. Metz, S. R. Saha, I.-L. Liu, M. Zic, H. Kim, J. Paglione, and N. P. Butch, Science 365, 684 (2019a).
  * Aoki  _et al._ [2019a] D. Aoki, A. Nakamura, F. Honda, D. Li, Y. Homma, Y. Shimizu, Y. J. Sato, G. Knebel, J.-P. Brison, A. Pourret, D. Braithwaite, G. Lapertot, Q. Niu, M. Valiska, H. Harima, and J. Flouquet, Journal of the Physical Society of Japan 88, 043702 (2019a).
  * Knebel  _et al._ [2019] G. Knebel, W. Knafo, A. Pourret, Q. Niu, M. Valiska, D. Braithwaite, G. Lapertot, M. Nardone, A. Zitouni, S. Mishra, I. Sheikin, G. Seyfarth, J.-P. Brison, D. Aoki, and J. Flouquet, Journal of the Physical Society of Japan 88, 063707 (2019).
  * Ran  _et al._ [2019b] S. Ran, I.-L. Liu, Y. S. Eo, D. J. Campbell, P. M. Neves, W. T. Fuhrman, S. R. Saha, C. Eckberg, H. Kim, D. Graf, F. Balakirev, J. Singleton, J. Paglione, and N. P. Butch, Nature Physics 15, 1250–1254 (2019b).
  * Aoki  _et al._ [2019b] D. Aoki, K. Ishida, and J. Flouquet, Journal of the Physical Society of Japan 88, 022001 (2019b).
  * Braithwaite  _et al._ [2019] D. Braithwaite, M. Vališka, G. Knebel, G. Lapertot, J.-P. Brison, A. Pourret, M. E. Zhitomirsky, J. Flouquet, F. Honda, and D. Aoki, Commun. Phys. 2, 147 (2019).
  * Ran  _et al._ [2020] S. Ran, H. Kim, I.-L. Liu, S. R. Saha, I. Hayes, T. Metz, Y. S. Eo, J. Paglione, and N. P. Butch, Phys. Rev. B 101, 140503(R) (2020).
  * Thomas  _et al._ [2020] S. M. Thomas, F. B. Santos, M. H. Christensen, T. Asaba, F. Ronning, J. D. Thompson, E. D. Bauer, R. M. Fernandes, G. Fabbris, and P. F. S. Rosa, (2020), arXiv:2005.01659 [cond-mat.str-el] .
  * Aoki  _et al._ [2020] D. Aoki, F. Honda, G. Knebel, D. Braithwaite, A. Nakamura, D. Li, Y. Homma, Y. Shimizu, Y. J. Sato, J.-P. Brison, and J. Flouquet, Journal of the Physical Society of Japan 89, 053705 (2020).
  * Lin  _et al._ [2020] W.-C. Lin, D. J. Campbell, S. Ran, I.-L. Liu, H. Kim, A. H. Nevidomskyy, D. Graf, N. P. Butch, and J. Paglione, (2020), arXiv:2002.12885 [cond-mat.supr-con] .
  * Knebel  _et al._ [2020] G. Knebel, M. Kimata, M. Vališka, F. Honda, D. Li, D. Braithwaite, G. Lapertot, W. Knafo, A. Pourret, Y. J. Sato, Y. Shimizu, T. Kihara, J.-P. Brison, J. Flouquet, and D. Aoki, Journal of the Physical Society of Japan 89, 053707 (2020).
  * Hayes  _et al._ [2020] I. M. Hayes, D. S. Wei, T. Metz, J. Zhang, Y. S. Eo, S. Ran, S. R. Saha, J. Collini, N. P. Butch, D. F. Agterberg, A. Kapitulnik, and J. Paglione, (2020), arXiv:2002.02539 [cond-mat.str-el] .
  * Jiao  _et al._ [2020] L. Jiao, S. Howard, S. Ran, Z. Wang, J. O. Rodriguez, M. Sigrist, Z. Wang, N. P. Butch, and V. Madhavan, Nature 579, 523 (2020).
  * Nakamine  _et al._ [2019] G. Nakamine, S. Kitagawa, K. Ishida, Y. Tokunaga, H. Sakai, S. Kambe, A. Nakamura, Y. Shimizu, Y. Homma, D. Li, F. Honda, and D. Aoki, Journal of the Physical Society of Japan 88, 113703 (2019).
  * Tou  _et al._ [1996] H. Tou, Y. Kitaoka, K. Asayama, N. Kimura, Y. Ōnuki, E. Yamamoto, and K. Maezawa, Odd-parity superconductivity with parallel spin pairing in ${\mathrm{upt}}_{3}$: Evidence from ${}^{195}\mathrm{Pt}$ knight shift study, Phys. Rev. Lett. 77, 1374 (1996).
  * Tou  _et al._ [1998] H. Tou, Y. Kitaoka, K. Ishida, K. Asayama, N. Kimura, Y. Ōnuki, E. Yamamoto, Y. Haga, and K. Maezawa, Nonunitary spin-triplet superconductivity in ${\mathrm{upt}}_{3}$: Evidence from ${}^{195}pt$ knight shift study, Phys. Rev. Lett. 80, 3129 (1998).
  * Hattori  _et al._ [2013] T. Hattori, K. Karube, Y. Ihara, K. Ishida, K. Deguchi, N. K. Sato, and T. Yamamura, Spin susceptibility in the superconducting state of the ferromagnetic superconductor ucoge, Phys. Rev. B 88, 085127 (2013).
  * Manago  _et al._ [2019] M. Manago, S. Kitagawa, K. Ishida, K. Deguchi, N. K. Sato, and T. Yamamura, Spin-triplet superconductivity in the paramagnetic ucoge under pressure studied by 59co nmr, Phys. Rev. B 100, 035203 (2019).
  * Leggett [1975] A. J. Leggett, A theoretical description of the new phases of liquid ${}^{3}\mathrm{He}$, Rev. Mod. Phys. 47, 331 (1975).
  * Tokunaga  _et al._ [2019] Y. Tokunaga, H. Sakai, S. Kambe, T. Hattori, N. Higa, G. Nakamine, S. Kitagawa, K. Ishida, A. Nakamura, Y. Shimizu, Y. Homma, D. Li, F. Honda, and D. Aoki, Journal of the Physical Society of Japan 88, 073701 (2019).
  * Momma and Izumi [2011] K. Momma and F. Izumi, Vesta 3 for three-dimensional visualization of crystal, volumetric and morphology data, J. Appl. Cryst. 44, 1272 (2011).
  * [22] See Supplemental Material at xxx for the details of the experimental setting and the temperature dependence of the NMR linewidth.
  * Hiranuma and Fujimoto [2020] K. Hiranuma and S. Fujimoto, (2020), arXiv:2010.05112v1 [cond-mat.supr-con] .
  * [24] P. G. de Gennes, Superconductivity of metals and alloys (w. a. benjamin inc., 1966).
  * Paulsen  _et al._ [2020] C. Paulsen, G. Knebel, G. Lapertot, D. Braithwaite, A. Pourret, D. Aoki, F. Hardy, J. Flouquet, and J. P. Brison, (2020), arXiv:2002.12724 [cond-mat.str-el] .
  * Ishizuka  _et al._ [2019] J. Ishizuka, S. Sumita, A. Daido, and Y. Yanase, Insulator-metal transition and topological superconductivity in ${\mathrm{ute}}_{2}$ from a first-principles calculation, Phys. Rev. Lett. 123, 217001 (2019).
  * Kittaka  _et al._ [2020] S. Kittaka, Y. Shimizu, T. Sakakibara, A. Nakamura, D. Li, Y. Homma, F. Honda, D. Aoki, and K. Machida, Phys. Rev. Research 2, 032014(R) (2020).
  * Tada  _et al._ [2016] Y. Tada, S. Takayoshi, and S. Fujimoto, Magnetism and superconductivity in ferromagnetic heavy-fermion system ucoge under in-plane magnetic fields, Phys. Rev. B 93, 174512 (2016).
  * Ishizuka and Yanase [2020] J. Ishizuka and Y. Yanase, (2020), arXiv:2008.01945 [cond-mat.supr-con] .

Supplemental Material

##  I The comparison of the 125Te-NMR spectrum with the previous report

Figure 5 shows normal-state 125Te-NMR spectra of a 125Te-enriched sample used
on this measurement and of a natural-Te sample used on the previous
measurement[1].

The NMR-signal intensity of the enriched sample is much stronger than that of
the previous sample, although the sample volume of two samples is almost the
same, In addition, the linewidth of the two samples is almost the same,
ensuring that the sample quality of the enriched one is unchanged with the
natural one.

Figure 5: Normal-state 125Te-NMR spectra of the 125Te-enriched sample used in
this study and of a natural-Te sample used on the previous measurement[1]. The
$\Delta f$ for horizontal axis is the difference in NMR frequency from the
peak position($\Delta f=f-f_{\rm peak}$).

##  II Alignment of the magnetic field

In order to apply magnetic field exactly parallel to the $b$ or $c$ axis, we
used the split superconducting (SC) magnet generating a horizontal field
combined with a single-axis rotator with the $a$-axis being the rotation axis.
Figure 6 shows the angular dependence of 125Te-NMR spectra (A) and the
resonance peaks (B) of both the Te(1) and Te(2) sites at 4.2 K under the field
of 1 T in the $bc$ plane. The obtained angular dependence is consistent with
the previous reports[2, 1]. As well as the previous study[1], we measured the
spectra near the $b$ axis with a small angle step and plotted the resonance
peak as shown in Fig. 6 (C), and aligned the field exactly parallel to the $b$
axis.

Figure 6: (A) The angular dependence of the 125Te-NMR spectra of both the
Te(1) and Te(2) sites at 4.2 K. The magnetic field is 1 T in the $bc$ plane.
(B) The angular dependence of the resonance peaks for both the Te(1) and Te(2)
sites. (C) The zoomed view of the angular dependence of the resonance
frequency of the Te(2) site around the $b$ axis.

##  III Evaluation of the Knight shift and linewidth of NMR spectrum in
$\bm{H\parallel c}$

As shown in Fig. S2, the Te(1) and Te(2) signals were distinct when
$H\parallel b$ but overlapped when $H\parallel c$. It is difficult to
distinguish between the two signals because the line width is broad in
$H\parallel c$. Therefore, we determined the Knight shift from the spectral-
peak frequency because the contribution of the Te(2) site was dominant even in
the broad spectrum when $H\parallel c$. In addition, we defined the linewidth
as the left-side half width at half maximum (LHWHM) as shown in the inset of
Fig. 7 to avoid the contribution of the Te(1) signal. The broken curves in
Figs. 1(D), 2(B), 2(C), and the inset of Fig. S3 indicating the Te(1) and
Te(2) sites are guide to eye and are depicted as follows. As seen in
$H\parallel b$, the signal intensity ratio of Te(1) and Te(2) is not 1:1 by
some reasons such as difference of nuclear spin-spin relaxation rate, and of
pulse conditions. Thus, the broken curves were determined by double Lorentzian
fitting with the fixed signal area ratio [Te(1)/Te(2) 0.56], referring to the
spectrum reported by Tokunaga et al.[2]

##  IV temperature dependence of the linewidth of the NMR spectrum

In general, the linewidth of the NMR spectrum becomes broader in the SC state
than that in the normal state, by the presence of the SC diamagnetic shielding
and the distribution of the spin susceptibility. Therefore, the broadening of
the linewidth below $T_{\rm c}$ is one of the reliable confirmation that the
NMR spectrum in the SC state is measured.

Figure 7: The temperature dependence of the increase of FWHM in the SC state
($\Delta$FWHM ) when $H\parallel b$ (A) and of the increase of left-side HWHM
in the SC state when $H\parallel c$ (B). $\Delta$FWHM is defined as
$\Delta$FWHM $\equiv$ FWHM($T$) - FWHM in the normal state. Dashed lines are
added as guide to eye and arrows show superconducting transition temperature
obtained from the AC susceptibility measurements. (inset) The typical NMR
spectrum in $H\parallel c$ to show the definition of left-side HWHM. Dotted
lines represents the result of fitting by the two-Lorentzian function.

Figure 7 shows the behavior of the linewidth increase of the NMR spectrum for
$H\parallel b$ (A) and $H\parallel c$ (B). The arrows in the figure show the
$T_{\rm c}$ determined with the AC susceptibility measurement. The full width
at the half maximum (FWHM) in $H\parallel b$ is obtained by the Gaussian
fitting of the whole spectrum. The FWHMs below $\sim 0.8$ K are not plotted
because a shoulder peak appears at the lower-frequency side (i.e. at the lower
Knight shift) than the original peak frequency below 0.9 K, as mentioned in
the main text. The spectrum in $H\parallel b$ is broadened from just below
$T_{\rm c}$. When $H\parallel c$, we plotted LHWHM as mentioned above. The
spectra in $H\parallel c$ is also broadened from just below $T_{\rm c}$, as in
the case when $H\parallel b$. The broadening of the spectrum from just below
$T_{\rm c}$ when $H\parallel b$ and $H\parallel c$ ensures that the NMR
spectrum in the SC state is certainly measured.

## References

  * Nakamine  _et al._ [2019] G. Nakamine, S. Kitagawa, K. Ishida, Y. Tokunaga, H. Sakai, S. Kambe, A. Nakamura, Y. Shimizu, Y. Homma, D. Li, F. Honda, and D. Aoki, Journal of the Physical Society of Japan 88, 113703 (2019).
  * Tokunaga  _et al._ [2019] Y. Tokunaga, H. Sakai, S. Kambe, T. Hattori, N. Higa, G. Nakamine, S. Kitagawa, K. Ishida, A. Nakamura, Y. Shimizu, Y. Homma, D. Li, F. Honda, and D. Aoki, Journal of the Physical Society of Japan 88, 073701 (2019).


# Stronger Coreset Bounds for Kernel Density Estimators via Chaining

Rainie Bozzai and Thomas Rothvoss

###### Abstract.

We apply the discrepancy method and a chaining approach to give improved
bounds on the coreset complexity of a wide class of kernel functions. Our
results give randomized polynomial time algorithms to produce coresets of size
$O\big{(}\frac{\sqrt{d}}{\varepsilon}\sqrt{\log\log\frac{1}{\varepsilon}}\big{)}$
for the Gaussian and Laplacian kernels in the case that the data set is
uniformly bounded, an improvement that was not possible with previous
techniques. We also obtain coresets of size
$O\big{(}\frac{1}{\varepsilon}\sqrt{\log\log\frac{1}{\varepsilon}}\big{)}$ for
the Laplacian kernel for $d$ constant. Finally, we give the best known bounds
of
$O\big{(}\frac{\sqrt{d}}{\varepsilon}\sqrt{\log(2\max\\{1,\alpha\\})}\big{)}$
on the coreset complexity of the exponential, Hellinger, and JS Kernels, where
$1/\alpha$ is the bandwidth parameter of the kernel.

This material is based upon work supported by the National Science Foundation
Graduate Research Fellowship under Grant No. DGE-2140004. R.B. is also
partially supported by Grant No. G20221001-4371 in Aid of Research from Sigma
Xi, The Scientific Research Honor Society. T.R. is supported by NSF grant
2318620 and a David & Lucile Packard Foundation Fellowship.

##  1\. Introduction

Kernel density estimators provide a non-parametric method for estimating
probability distributions. In contrast to parametric machine learning models,
in which a set of training data is used to determine an optimal parameter
vector which can be used to predict future outcomes without the training data,
for non-parametric methods the number of parameters of the model has the
capability to grow as the size of the dataset grows. Our paper will focus on
the task of kernel density estimation, in which one estimates a probability
distribution using kernel functions of the form
$\mathcal{K}:\mathcal{D}\times\mathcal{D}\rightarrow\mathbb{R}$. Kernels are
often defined with a bandwidth parameter $1/\alpha$ that controls the width of
the kernel function.

Given a probability distribution $\rho$ and a collection of points
$X=\\{x_{1},...,x_{n}\\}\sim\rho$ sampled independently, it is well known that
for certain well-behaved kernel functions $K$, the distribution $\rho$ can be
approximated very well by the kernel density estimator (KDE)

$\mathrm{KDE}_{X}(y)=\frac{1}{n}\sum_{i\in[n]}K(x_{i},y).$

In particular, it is known that under certain conditions on the kernel
function, $\mathrm{KDE}_{X}$ approximates $\rho$ at the minimax optimal rate
as $|X|\rightarrow\infty$ [26].

Although this is an elegant theoretical result, in practice it is
computationally inefficient to store and make computations with an arbitrarily
large number of data points $n$. One solution to reduce the computational
complexity is to use an $\varepsilon$-coreset for a kernel density estimator.

######  Definition 1.1 (KDE $\varepsilon$-coreset).

For fixed $\varepsilon>0$, kernel function
$K:\mathcal{D}\times\mathcal{D}\to\mathbb{R}$, and data set
$X\subseteq\mathcal{D}$, an _$\varepsilon$ -coreset_ for $K$ is a subset
$Q\subseteq X$ so that

$\|\mathrm{KDE}_{X}(y)-\mathrm{KDE}_{Q}(y)\|_{\infty}=\sup_{y\in\mathcal{D}}\Big{|}\frac{1}{|X|}\sum_{x\in
X}K(x,y)-\frac{1}{|Q|}\sum_{q\in Q}K(q,y)\Big{|}\leq\varepsilon.$

We will say that the coreset complexity of a kernel function $K$ is the
minimum possible size of a $\varepsilon$-coreset $Q$ for $K$.

In general, coreset complexity bounds will depend on $\varepsilon$ and the
dimension $d$ of the kernel domain, and they will be independent of the size
of the set $X$. These bounds are also often independent of the choice of
$X\subseteq\mathcal{D}$, although several previous results and several of our
results give an explicit dependence on $X$ that may allow improvement over
existing bounds for sufficiently nice data sets (see Section 1.3). In
particular, several of our bounds will depend on the radius of the set $X$.

For more details about non-parametric methods and kernel density estimation,
see for example [26].

###  1.1. The Discrepancy Approach

One powerful method for proving bounds on the coreset complexity of kernel
functions is the discrepancy approach. It has also been used in [19, 25, 21,
14] and is based on a method for computing range counting coresets [7, 21, 6,
20]. Following the notational conventions of [19], we make the following
definition.

######  Definition 1.2 (Kernel Discrepancy).

Given a data set $X\subseteq\mathcal{D}$, a kernel
$K:\mathcal{D}\times\mathcal{D}\rightarrow\mathbb{R}$, and a coloring
$\beta\in\\{\pm 1\\}^{X}$, the kernel discrepancy at a point $y\in\mathcal{D}$
is defined as

$\mathrm{disc}_{K}(X,\beta,y):=\Big{|}\sum_{x\in X}\beta(x)K(x,y)\Big{|}.$

Then the kernel discrepancy can then be defined as

$\mathrm{disc}_{K}(n)=\max_{\begin{subarray}{c}X\subseteq\mathcal{D}:\\\ \
|X|=n\end{subarray}}\min_{\beta\in\\{\pm 1\\}^{X}}\max_{y\in\mathcal{D}}\
\mathrm{disc}_{K}(X,\beta,y).$

We will also use the notation $\mathrm{disc}_{K}(X)$ to denote the kernel
discrepancy with respect to a fixed data set $X$. Bounds on kernel discrepancy
can be leveraged to obtain bounds on the coreset complexity for a given kernel
$K$ via the following strategy, often called the “halving trick” [7, 6, 20].
We construct a coreset of $X$ by iteratively removing half of the points in
$X$, and we select which half of the points are removed by creating colorings
$\beta\in\\{\pm 1\\}^{X}$ minimizing the kernel discrepancy and then removing
those points assigned $-1$ (in principle, there is no reason to expect that
exactly half of the points are assigned $+1$, and half $-1$, but there are
standard techniques to overcome this challenge [17]). Indeed, supposing that
we have an optimal choice of signs $\beta\in\\{\pm 1\\}^{X}$ such that

$\sup_{y\in\mathcal{D}}\Big{|}\sum_{x\in X}\beta(x)K(x,y)\Big{|}\leq f(n),$

then we simply note that, letting $X^{+}$ be the set of points assigned $+1$
and $X^{-}$ be the set of points assigned $-1$, then under the assumption that
$|X^{-}|=|X|/2$, for any $y\in\mathcal{D}$,

$\displaystyle\begin{split}\frac{1}{|X|}\sum_{x\in
X}\beta(x)K(x,y)&=\frac{1}{|X|}\sum_{x\in X^{+}}K(x,y)-\frac{1}{|X|}\sum_{x\in
X^{-}}K(x,y)\\\ &=\frac{1}{|X|}\sum_{x\in X}K(x,y)-\frac{1}{|X|/2}\sum_{x\in
X^{-}}K(x,y).\end{split}$ (1)

Taking a supremum over $y\in\mathcal{D}$, the final line of (1) is exactly
$\mathrm{KDE}_{X}(y)-\mathrm{KDE}_{X^{-}}(y)$. Thus, iterating this procedure
$t$ times, and denoting the resulting set at iteration $s$ by $X_{s}$ (with
$X_{0}:=X$), we find that

$\|\mathrm{KDE}_{X}-\mathrm{KDE}_{X_{t}}\|_{\infty}\leq\sum_{s\in[t]}\|\mathrm{KDE}_{X_{s-1}}-\mathrm{KDE}_{X_{s}}\|_{\infty}\leq\sum_{s\in[t]}\frac{2^{s-1}}{n}f\big{(}n/2^{s-1}\big{)}.$

Assuming that the function $f$ grows sufficiently slowly111It suffices if
$f(n)\leq n^{c}$ for some fixed constant $0<c<1$., this sum will be dominated
by the final term, which allows us to calculate the size of a coreset yielding
error at most $\varepsilon$. Based on this connection, our proofs will focus
on bounding the quantity $\mathrm{disc}_{K}(n)$ for different kernels $K$ (or
in some cases $\mathrm{disc}_{K}(X)$, when we want to account for the geometry
of the data set $X$), and then the “halving trick” can easily be used to
determine the corresponding size of the coreset thus obtained.

###  1.2. Positive Definite Kernels and Reproducing Kernel Hilbert Spaces

A kernel $K:\mathcal{D}\times\mathcal{D}\rightarrow\mathbb{R}$ is said to be
positive definite if given any selection of points
$x_{1},...,x_{m}\in\mathcal{D}$, the Gram matrix $G$ given by
$G_{ij}=K(x_{i},x_{j})$ is positive definite. The importance of our assumption
that our kernels are positive definite rests on the following famous theorem
[1].

######  Theorem 1.3 (Moore-Aronszajn, 1950).

Let $T$ be a set and $K$ a positive definite function on $T\times T$. Then
there is a map $\phi:T\rightarrow\mathcal{H}_{K}$ to a unique corresponding
Hilbert space $\mathcal{H}_{K}$ so that for any $s,t\in T$,

$K(s,t)=\langle\phi(s),\phi(t)\rangle_{\mathcal{H}_{K}}.$

The Hilbert space $\mathcal{H}_{K}$ is called the reproducing kernel Hilbert
space (RKHS) associated to $K$. Using this theorem, we can make the following
definition:

######  Definition 1.4.

The kernel distance associated to a kernel function $K$ is the function

$D_{K}(x,y):=\|\phi(x)-\phi(y)\|_{\mathcal{H}_{K}}.$

Here $\|h\|_{\mathcal{H}_{K}}=\sqrt{\langle h,h\rangle_{\mathcal{H}_{K}}}$ is
the Euclidean norm in $\mathcal{H}_{K}$. In general, it is only true that
$D_{K}$ is a pseudometric on the domain of $K$; however, this is all we will
need for our proofs. Almost all of the kernels commonly used in machine
learning applications are positive definite.

###  1.3. Summary of Known Results

The problem of coreset complexity for a wide variety of kernel functions has
been studied for several decades. Early approaches focused on random samples
[23, 22, 12], but more recently analytic approaches and new algorithms have
been discovered, leading to much stronger bounds. We provide a brief summary
of these results, which apply a wide range of techniques and apply to various
classes of kernels.

Joshi et al. [13] used a sampling technique to prove a bound of
$O((1/\varepsilon^{2})(d+\log(1/\delta)))$ on the coreset complexity of any
centrally symmetric, non-increasing kernel, where $\delta$ is the probability
of failure. Fasy et al. [10] used sampling to prove a different bound of
$O((d/\varepsilon^{2})\log(d\Delta/\varepsilon\delta))$, where
$\Delta:=\alpha\sup_{x,x^{\prime}\in X}\|x-x^{\prime}\|_{2}$ is the diameter
of the data set. This result may improve upon that of Joshi et al. in the case
that $K(x,x)>1$, and it also applies to the broader class of Lipschitz
kernels.

The following collection of results applies to the collection of
_characteristic kernels_ , a subset of positive definite kernels that satisfy
the additional property that the mapping $\phi_{K}$ into the associated RKHS
is injective, which implies that the induced kernel distance $D_{K}$ is a
metric. This class contains many, though not all, positive definite kernels,
with a notable exception being the exponential kernel (see Theorem 1.11).
Again using random sampling, Lopaz-Paz et al. [16, 18] gave a simpler bound of
$O((1/\varepsilon^{2})\log(1/\delta))$.

Improved results were proved using an iterative technique called kernel
herding introduced by Chen et al. [8] to solve a closely related problem
called kernel mean approximation, which is shown to upper bound kernel density
approximation in the case of reproducing kernels [8, 24]. Chen et al. proved a
bound of $O(1/(\varepsilon r_{X}))$, where $r_{X}$ is the largest radius of a
ball centered at $\frac{1}{|X|}\sum_{x\in X}\phi_{K}(x)\in\mathcal{H}_{K}$
that is completely contained in $\mathrm{conv}\\{\phi(x):\ x\in X\\}$. This
paper claimed that $r_{X}$ is always a constant greater than $0$; however,
Bach et al. [3] gave a new interpretation of the algorithm and argued that
although $r_{X}$ is arbitrarily small for continuous distributions, the
constant $1/r_{X}$ is finite when $X$ is finite. Their interpretation provided
a bound of $(1/r_{X}^{2})\log(1/\varepsilon)$. Bach et al. also provided a
bound of $O(1/\varepsilon^{2})$ in the case of weighted coreset complexity,
where points in $X$ can be assigned a non-negative weight, and this result was
later improved to the setting of unweighted coresets [15].

Harvey and Samadi [11] applied the kernel herding technique to an even more
general problem called general mean approximation in $\mathbb{R}^{d}$ to
provide bounds on the coreset complexity of order
$O((1/\varepsilon)\sqrt{n}\log^{2.5}(n))$, where $n=|X|$. The dependence on
$n$ is introduced by the worst case outcome of manipulating $r_{X}$ using
affine scaling. Locoste-Julien et al. [15] showed that actually one can take
$n=O(1/\varepsilon^{2})$ which improves the bound to
$O((1/\varepsilon^{2})\log^{2.5}(1/\varepsilon))$.

The next collection of bounds applies to _Lipschitz kernels_ , that is,
kernels where we can bound the Lipschitz factor
$C_{K}:=\max_{x,y,z\in\mathcal{D}}\frac{\|K(z,x)-K(z,y)\|_{2}}{\|x-y\|_{2}}$
of $K$. In the case that $C_{K}$ is a small constant, as is the case for most
kernels of interest, it is easy to see that taking a
$2\varepsilon/(C_{K}\sqrt{d})$-net $G_{\varepsilon}$ over the domain of $K$
and mapping each point $x\in X$ to the closest point in $G_{\varepsilon}$
(with multiplicity) to obtain $X_{G_{\varepsilon}}$, we find that
$\sup_{y\in\mathcal{D}}|\mathrm{KDE}_{X}(y)-\mathrm{KDE}_{X_{G_{\varepsilon}}}(y)|\leq\varepsilon$.
Cortes and Scott’s work on the sparse kernel mean problem [9] combined with
the discretization argument above implies a bound of
$O((\Delta/\varepsilon)^{d})$ on the coreset-complexity, in the case that
$\Delta$ is bounded.

Phillips [21] | $O((\alpha/\varepsilon)^{2d/(d+2)}\log^{d/(d+2)}(\alpha/\varepsilon))$ | Lipschitz, PD
---|---|---
Phillips and Tai [19] | $\sqrt{d\log n}$ | Lipschitz, PD
Tai [25] | $2^{O(d)}$ | Gaussian
New | $2^{O(d)}\sqrt{\log\log n}$ | Laplacian
New | $O(\sqrt{d\log(\mathrm{radius}X+\log n)})$ | Gaussian, Laplacian
New | $O(\sqrt{d\log(2\max\\{\alpha,1\\})})$ | Exponential, JS, Hellinger
Table 1. Results from the Discrepancy Approach

Also in the setting of Lipschitz kernels, but now using the discrepancy-based
approach described in Section 1.1, Phillips [21] showed a bound of

$O((\alpha/\varepsilon)^{2d/(d+2)}\log^{d/(d+2)}(\alpha/\varepsilon))$

for kernels with a Lipchitz factor $C_{K}=O(\alpha)$. Using a sorting
argument, Phillips also showed in this paper that for $d=1$ one can achieve a
coreset of size $O(1/\varepsilon)$, matching a tight lower bound. Note that in
general the coreset complexity is always bounded below by $O(1/\varepsilon)$,
as can be seen by taking $O(1/\varepsilon)$ points that are spread far apart
[21]. Phillips and Tai [19] improved these results by combining the
discretization approach with the discrepancy approach to give a bound of
$O((1/\varepsilon)\sqrt{d\log(1/\varepsilon)})$ for any positive definite,
Lipschitz kernel with bounded influence, a restriction similar to the impact
radius condition that we will define. This result applies to a very wide class
of kernels, including all of the kernels that we will discuss in our paper,
and also the sinc kernel, for which no earlier non-trivial bounds were known.
They also provide a lower bound of $\Omega(\sqrt{d}/\varepsilon)$ for
$d\in[2,1/\varepsilon^{2})$, and a tight lower bound of $O(1/\varepsilon^{2})$
in the case that $d\geq 1/\varepsilon^{2}$, for all shift and rotation
invariant kernels that are somewhere-steep. Tai [25] later proved that for $d$
constant, the Gaussian kernel has coreset complexity $O(1/\varepsilon)$,
matching the optimal lower bound in terms of $\varepsilon$. This result
supresses an exponential dependence on $d$, but is still interesting for
small-dimensional data sets.

Finally, a related but not directly comparable result due to Karnin and
Liberty [14] applies to kernels that are analytic functions of the dot product
and satisfy the very strong condition that
$\sup_{x,x^{\prime}\in\mathcal{D}}\|x-x^{\prime}\|_{2}\leq R_{K}$, where
$R_{K}$ is a fixed constant determined by the kernel $K$. In this setting,
they show a bound of $O(\sqrt{d}/\varepsilon)$ on the coreset complexity.
However, as we will see, for kernels such as the Gaussian or Laplacian kernel,
one can only assume that
$\sup_{x,x^{\prime}\in\mathcal{D}}\|x-x^{\prime}\|_{2}\leq n\log n$, where
$n=|X|$, and thus this result does not apply. Their result can however be
interpreted to give a bound of $O(\alpha\exp(\alpha)\sqrt{d}/\varepsilon)$ on
the coreset complexity of the exponential kernel, as in this case the domain
of the kernel function does have constant diameter.

###  1.4. Our Contributions

Our results require the following two definitions.

######  Definition 1.5 (Impact Radius).

Given a kernel $K:\mathcal{D}\times\mathcal{D}\rightarrow\mathbb{R}$ for
$\mathcal{D}\subseteq\mathbb{R}^{d}$, we define the impact radius of $K$ as

$r_{K}(n):=\inf\big{\\{}r\geq 0:\ \|x-y\|_{2}\geq r\ \implies\ |K(x,y)|\leq
1/n\ \ \forall x,y\in\mathcal{D}\big{\\}}.$

######  Definition 1.6 (Query Space).

Given a kernel $K:\mathcal{D}\times\mathcal{D}\rightarrow\mathbb{R}$ and a
data set $X\subseteq\mathcal{D}$, we define the query space of $K$ with
respect to $X$ as

$Q=\Big{\\{}y\in\mathcal{D}:\ \exists x\in X\ \mbox{s.t.}\ \|x-y\|_{2}\leq
r_{K}(|X|)\Big{\\}}=\mathcal{D}\cap\Big{(}\bigcup_{x\in
X}(x+r_{K}(|X|)B_{2}^{d})\Big{)}.$

Note that in general both the impact radius and the query space may depend
explicitly on the bandwidth parameter $\alpha$, but this dependence often
cancels out, making the bounds obtained independent of $\alpha$. One notable
exception where this cancellation does not occur is when the domain
$\mathcal{D}$ of the kernel is compact, for example for the exponential,
Hellinger, and Jensen-Shannon kernels; we return to this idea in Sections 4
and 5. We also note that in the event that the query space $Q$ given by a
particular data set is disconnected, it suffices to consider the largest
connected component of $Q$. To see this, note that by the definition of impact
radius, the query points and data points from distinct connected components do
not interact, thus we can apply the same bound to each connected component
independently. For the proof of our results, we will assume that $Q$ is
connected.

Our two main results will be in terms of the size of the query space and the
impact radius of the kernel, respectively. One of the key challenges in
earlier applications of the discrepancy approach was that the domain
$\mathcal{D}$ is often $\mathbb{R}^{d}$, the sphere $S^{d}$, the standard
$(d-1)$-dimensional simplex $\Delta^{d}$, or some other potentially unbounded
and/or uncountably infinite space. These domains make bounding the discrepancy
challenging, as probabilistic techniques are often used, and the size of these
spaces make the union bound ineffective. The following lemma shows how the
query space and impact radius can simplify this problem to at least ensure
that the domain is bounded for kernels with sufficiently nice decay
properties.

######  Lemma 1.7.

Let $K:\mathcal{D}\times\mathcal{D}\to\mathbb{R}$ be a kernel,
$X\subseteq\mathcal{D}$ a data set, and $Q$ the query space associated to $K$
and $X$. Then

$\mathrm{disc}_{K}(n)\leq\mathrm{disc}_{K|_{Q}}(n)+O(1).$

###### Proof.

To prove the lemma, it suffices to show that for any $y\in\mathcal{D}\setminus
Q$, $\mathrm{disc}_{K}(X,\beta,y)=O(1)$ for all $\beta\in\\{\pm 1\\}^{X}$. But
this follows immediately, as we know by the definition of $Q$ that for any
$y\in\mathcal{D}\setminus Q$ and $x\in X$, $|K(x,y)|\leq 1/n$. Thus

$\mathrm{disc}_{K}(X,\beta,y)=\Big{|}\sum_{x\in
X}\beta(x)K(x,y)\Big{|}\leq\sum_{x\in X}|K(x,y)|\leq 1.\qed$

Earlier approaches using the discrepancy approach [19, 25] needed an even
stronger version of Lemma 1.7 for Lipschitz kernels that also ensured that the
query space could be made finite up to an $O(1)$ error using the Lipschitz
constant of the kernel and a sufficiently small $\varepsilon$-net. This lemma
provides an extra factor of $\sqrt{\log n}$ in many results that we will avoid
by using chaining [27], a multi-step construction of $\varepsilon$-nets. Note
that in general, for an arbitrary data set, the query space can have volume up
to $n\mathrm{Vol}_{d}(r_{K}B_{2}^{d})$, as it is possible that the data points
are well spread out and thus the impact radii of data points do not intersect.
This observation is why [14] cannot be applied to the general Gaussian kernel,
for example.

Our first result gives a discrepancy bound that depends explicitly on the
choice of the data set $X\subseteq\mathbb{R}^{d}$.

######  Theorem 1.8.

Let $K:\mathbb{R}^{d}\times\mathbb{R}^{d}\rightarrow\mathbb{R}$ be a kernel
with bandwidth parameter $1/\alpha$ and $X\subseteq\mathbb{R}^{d}$ be a
dataset. Denote the query space of $(K,X)$ by $Q$, and define $R=R(X)$ so that
$Q\subseteq RB_{2}^{d}$. If $K$ satisfies the following properties:

  1. (i)

$K$ is positive definite;

  2. (ii)

$K$ satisfies $K(x,x)=1$ for all $x\in Q$;

  3. (iii)

$K=\kappa(\alpha\|x-y\|_{2})$, where $\kappa:\mathbb{R}_{\geq
0}\rightarrow[-1,1]$ is strictly decreasing and continuous; and

  4. (iv)

The following bound holds, where $[0,b_{K})$ is the domain of the integrand:

$\int_{0}^{b_{K}}\sqrt{-\ln\left[\kappa^{-1}\left(\frac{2-r^{2}}{2}\right)\right]}\mathrm{d}r=O(1);$

then

$\mathrm{disc}_{K}(X)=O(\sqrt{d\log(2\max\\{R\alpha,1\\})}).$

Moreover, there is a randomized algorithm that on input of $X$ and $K$, finds
an according coloring $\beta\in\\{\pm 1\\}^{X}$ in polynomial time.

We will see in Section 4 that Theorem 1.8 can give strong improvements on the
current best known bounds on the coreset complexity for the Gaussian and
Laplacian kernels in the case that the data set $X$ has bounded diameter. In
particular, we have the following corollary.

######  Corollary 1.1.

Let $K$ be a kernel satisfying the conditions of Theorem 1.8, and let
$X\subseteq\mathbb{R}^{d}$ be any data set. Then

$\mathrm{disc}_{K}(X,n)\leq
O(\sqrt{d\log(\mathrm{radius}(X)+\kappa^{-1}(1/n))}).$

Note that because of the discretization necessary to prove Phillip and Tai’s
bounds [19], even in the case where the data set is bounded uniformly, the
$\sqrt{\log n}$ factor in their discrepancy bound cannot be removed.

In the case where we do not want to account for the geometry of the data set
$X$, we present the following stronger bound in the case that the dimension
$d$ is taken to be constant.

######  Theorem 1.9.

Let $K:\mathbb{R}^{d}\times\mathbb{R}^{d}\rightarrow\mathbb{R}$ be a kernel
with bandwidth parameter $1/\alpha$ and $X\subseteq\mathbb{R}^{d}$ a data set.
If $K$ satisfies the following properties:

  1. (i)

$K$ is positive definite;

  2. (ii)

$K$ satisfies $K(x,x)=1$ for all $x\in Q$;

  3. (iii)

$K=\kappa(\alpha\|x-y\|_{2})$, where $\kappa:\mathbb{R}_{\geq
0}\rightarrow[-1,1]$ is strictly decreasing and continuous; and

  4. (iv)

The following bound holds:

$\int_{0}^{b_{K}}\sqrt{-\ln\left[\kappa^{-1}\left(\frac{2-r^{2}}{2}\right)\right]}\mathrm{d}r=O(1);$

then

$\mathrm{disc}_{K}(n)=2^{O(d)}\sqrt{\log(\kappa^{-1}(1/n))}.$

Moreover, there is a randomized algorithm that on input of $X$ and $K$, finds
an according coloring $\beta\in\\{\pm 1\\}^{X}$ in polynomial time.

We will see in Section 4 that Theorem 1.9 yields significantly stronger bounds
than [19] for several important kernels in machine learning, assuming the data
is sufficiently low dimensional.

Our last three results demonstrate that in cases where the kernel is not a
function of the Euclidean distance, a similar technique can still provide
strong bounds. In particular, we give $O(\sqrt{d})$ bounds for the Jensen-
Shannon, exponential, and Hellinger kernels, with a logarithmic dependence on
the bandwidth parameter $\alpha$. We define
$\Delta_{d}:=\\{x\in\mathbb{R}^{d}_{\geq 0}\mid\sum_{i\in[d]}x_{i}=1\\}$ as
the _standard_ $(d-1)$-_dimensional simplex_ in $\mathbb{R}^{d}$.

######  Theorem 1.10.

The Jensen-Shannon (JS) kernel

$K_{JS}:\Delta_{d}\times\Delta_{d}\rightarrow\mathbb{R},\ \ \
K_{JS}(x,y)=\exp\left(-\alpha\big{(}H\big{(}\tfrac{x+y}{2}\big{)}-\tfrac{H(x)+H(y)}{2}\big{)}\right),$

where $H(x)=-\sum_{i\in[d]}x_{i}\log x_{i}$ is the Shannon entropy function,
has discrepancy satisfying

$\mathrm{disc}_{K_{JS}}(n)=O(\sqrt{d\log(2\max\\{\alpha,1\\})}).$

Further, the JS Kernel has coreset complexity

$O(\sqrt{d\log(2\max\\{\alpha,1\\})}/\varepsilon),$

and such a coreset can be constructed in randomized polynomial time.

This result greatly improves on the current best bound of $O(\sqrt{d\log n})$
on the discrepancy of the JS kernel, in particular by dropping all dependence
on the size $n$ of the data set. We note that as the JS kernel is not shift or
rotation invariant, it is not known to satisfy any lower bounds other than
$O(1/\varepsilon)$, which holds for all kernels.

We also have the same bound for the exponential kernel.

######  Theorem 1.11.

The exponential kernel

$K_{e}:S^{d}\times S^{d}\rightarrow\mathbb{R},\ \ \
K_{e}(x,y)=\exp(-\alpha(1-\langle x,y\rangle)),$

has discrepancy satisfying

$\mathrm{disc}_{K_{e}}(n)=O(\sqrt{d\log(2\max\\{\alpha,1\\})}).$

Further, the exponential kernel has coreset complexity

$O(\sqrt{d\log(2\max\\{\alpha,1\\})}/\varepsilon),$

and such a coreset can be constructed in randomized polynomial time.

As we mentioned in Section 1.3, Karnin and Liberty’s proof technique in [14]
gives a bound of $O(\alpha\exp(\alpha)\sqrt{d})$ on this quantity, hence our
analysis gives a doubly-exponential improvement in terms of the bandwidth
parameter $\alpha$.

As a corollary of Theorem 1.11 we obtain the same bound for the Hellinger
kernel, again giving the best known result for this kernel.

######  Theorem 1.12.

The Hellinger kernel

$K_{H}:\Delta^{d}\times\Delta^{d}\rightarrow\mathbb{R},\ \ \
K_{H}(x,y)=\exp\left(-\alpha\sum_{i=1}^{d}\big{(}\sqrt{x}-\sqrt{y}\big{)}\right),$

has discrepancy satisfying

$\mathrm{disc}_{K_{H}}(n)=O(\sqrt{d\log(2\max\\{\alpha,1\\})})$

Further, the Hellinger kernel has coreset complexity

$O(\sqrt{d\log(2\max\\{\alpha,1\\})}/\varepsilon),$

and such a coreset can be constructed in randomized polynomial time.

As for the JS kernel, no better lower bound than $O(1/\varepsilon)$ is known
on the coreset complexity of the exponential and Hellinger kernels.

##  2\. Preliminaries

In this section we introduce several results from discrepancy theory that will
be essential in our proofs.

###  2.1. Banaszczyk’s Theorem and the Gram-Schmidt Walk

As we always work with positive definite kernels, by Theorem 1.3 each kernel
$K$ has an associated RKHS $\mathcal{H}_{K}$ and a map
$\phi_{K}:\mathcal{D}\rightarrow\mathcal{H}_{K}$. Having mapped the data set
$X$ into $\mathcal{H}_{K}$ via $\phi_{K}$, a key step of our analysis will be
to apply Banaszczyk’s theorem [4], in its algorithmic form [5], to the vectors
$\\{\phi_{K}(x):\ x\in X\\}$, which we observed above have norm $1$ for any
kernel satisfying $K(x,x)=1$ for $x\in\mathcal{D}$. The algorithmic variant of
Banaszczyk’s Theorem can be stated as follows.

######  Theorem 2.1 (Gram-Schmidt Walk [5]).

There is a polynomial-time randomized algorithm that takes as input vectors
$v_{1},\ldots,v_{n}\in\mathbb{R}^{m}$ of $\ell_{2}$ norm at most $1$ and
outputs random signs $\beta\in\\{\pm 1\\}^{n}$ such that the (mean zero)
random variable $\sum_{i=1}^{n}\beta_{i}v_{i}$ is $O(1)$-subgaussian.

We give one of several equivalent definitions of subgaussian random variables,
as well as the definition of the subgaussian norm, which we will need in
Section 2.2 (see [27] for more details).

######  Definition 2.2.

A random variable $X$ is _$K$ -subgaussian_ if the tails of $X$ satisfy

$\mathbb{P}[|X|\geq t]\leq 2\exp(-t^{2}/K^{2})\ \ \forall t\geq 0.$

The subgaussian norm of $X$ is then

$\|X\|_{\psi_{2}}:=\inf\\{s>0:\ \mathbb{P}[|X|\geq t]\leq 2\exp(-t^{2}/s^{2})\
\ \forall t\geq 0\\}.$

###  2.2. Chaining and Dudley’s Theorem

As we mentioned in Section 1.4, one of the key factors contributing to the
factor of $\sqrt{\log n}$ in [19] is the necessity of introducing a $1/n$-net
on the query space. This net necessitates at least $O(n^{d})$ data points in
the query space, which is precisely the factor yielding $\sqrt{d\log n}$, as
the final bound is proportional to $\sqrt{\log|Q|}$. To avoid this extra
factor of $\sqrt{\log(n)}$, we replace the union bound-type argument of [19]
by a _chaining_ approach. The term chaining refers to the fact that rather
than applying an $\varepsilon$-net to the entire space, we continue to
construct finer and finer $\varepsilon$-nets. For more details see [27].

######  Definition 2.3.

Given a (pseudo)metric space $(T,d)$ and $r>0$:

  * •

$B_{d}(s,r)=\\{t\in T:\ d(s,t)\leq r\\}$;

  * •

$\mathrm{diam}(d):=\sup_{t,s\in T}d(t,s)$;

  * •

$\mathcal{N}(T,d,r)$ is the size of a minimal $r$-cover of $T$ w.r.t. $d$,
i.e.

$\mathcal{N}(T,d,r)=\min\Big{\\{}|S|:\ S\subseteq T,\ T\subseteq\bigcup_{s\in
S}B_{d}(s,r)\Big{\\}}.$

######  Theorem 2.4 (Dudley’s Integral Inequality).

Let $(X_{t})_{t\in T}$ be a random process on a pseudometric space $(T,d)$
satisfying

$\|X_{t}-X_{s}\|_{\psi_{2}}\leq d(t,s)\ \ \forall t,s\in T.$

Then for any $t_{0}\in T$,

$\mathbb{E}\sup_{t\in
T}|X_{t}-X_{t_{0}}|\lesssim\int_{0}^{\mathrm{diam}(d)}\sqrt{\log\mathcal{N}(T,d,r)}\
\mathrm{d}r.$

For our application we need to control the absolute value which can be done as
follows:

######  Theorem 2.5 (Dudley’s Integral Inequality II).

Let $(X_{t})_{t\in T}$ be a random process on a pseudometric space $(T,d)$
satisfying

$\|X_{t}-X_{s}\|_{\psi_{2}}\leq d(t,s)\ \ \forall t,s\in T.$

Then for any $t_{0}\in T$,

$\mathbb{E}\sup_{t\in
T}|X_{t}|\lesssim\int_{0}^{\mathrm{diam}(d)}\sqrt{\log\mathcal{N}(T,d,r)}\
\mathrm{d}r+\|X_{t_{0}}\|_{\psi_{2}}.$

###### Proof.

By the triangle inequality $\mathbb{E}\sup_{t\in
T}|X_{t}|\leq\mathbb{E}\sup_{t\in
T}|X_{t}-X_{t_{0}}|+\mathbb{E}[|X_{t_{0}}|]$. The claim then follows from
Theorem 2.4 and the fact that
$\mathbb{E}[|X_{t_{0}}|]\lesssim\|X_{t_{0}}\|_{\psi_{2}}$. ∎

There is also a concentration version of this inequality.

######  Theorem 2.6 (Concentration Version of Dudley’s Inequality).

Let $(X_{t})_{t\in T}$ be a random process on a pseudometric space $(T,d)$
satisfying

$\|X_{t}-X_{s}\|_{\psi_{2}}\leq d(t,s)\ \forall t,s\in T.$

Then, for every $u\geq 0$, the event

$\sup_{t,s\in T}|X_{t}-X_{s}|\leq
C\left[\int_{0}^{\mathrm{diam}(T)}\sqrt{\log\mathcal{N}(T,d,r)}\ \mathrm{d}r\
+\ u\cdot\mathrm{diam}(T)\right]$

holds with probability at least $1-2\exp(-u^{2})$, where $C>0$ is a universal
constant.

We will see that condition (iv) in Theorems 1.8 and 1.9 is exactly the
quantity that will appear in the integral of interest once we make a
comparison between the pseudometric $D_{K}$ and the Euclidean distance. For
this comparison we will also need the following facts about covering numbers
[2].

######  Lemma 2.7.

Let $N(A,B)$ denote the number of copies of body $B$ needed to cover $A$. For
any convex set $K\subseteq\mathbb{R}^{d}$ and $r>0$, one has

$N(K,rB_{2}^{d})\leq
2^{d}\frac{\mathrm{Vol}_{d}(K+\tfrac{r}{2}B_{2}^{d})}{\mathrm{Vol}_{d}(rB_{2}^{d})}.$

######  Lemma 2.8.

For any symmetric convex body $P\subseteq\mathbb{R}^{d}$ and $r>0$, one has

$N(P,rP)\leq\Big{(}1+\frac{2}{r}\Big{)}^{d}.$

##  3\. Proofs of Theorems 1.8 and 1.9

We begin with the proof of Theorem 1.8.

###### Proof of Theorem 1.8.

We may assume that $R\alpha\geq 1$, otherwise replace $R$ by
$\frac{1}{\alpha}$. Let
$K:\mathbb{R}^{d}\times\mathbb{R}^{d}\rightarrow\mathbb{R}$ and
$X\subseteq\mathbb{R}^{d}$ satisfy conditions (i)-(iv) outlined in Theorem
1.8. As $K$ is positive definite, there exists an RKHS $\mathcal{H}_{K}$ and a
map $\phi:\mathbb{R}^{d}\rightarrow\mathcal{H}_{K}$ so that

$K(x,y)=\langle\phi(x),\phi(y)\rangle_{\mathcal{H}_{K}}\ \ \forall
x,y\in\mathbb{R}^{d}.$

We apply the Gram-Schmidt walk from Theorem 2.1 to the vectors $\phi(x)$ for
$x\in X$, noting that by condition (ii), $\|\phi(x)\|_{\mathcal{H}_{K}}=1$ for
each $x\in X$. The algorithm yields a distribution $\mathcal{P}$ over $\\{\pm
1\\}^{X}$ so that the random variable $\Sigma:=\sum_{x\in X}\beta(x)\phi(x)$,
with $\beta\sim\mathcal{P}$, is $O(1)$-subgaussian. In particular, as we know
that $\|\phi(y)\|_{\mathcal{H}_{K}}=1$ for any $y\in Q$, the (mean zero)
random variable

$\Sigma_{y}:=\big{\langle}\Sigma,\phi(y)\big{\rangle}=\sum_{x\in
X}\beta(x)K(x,y)=\mathrm{disc}_{K}(X,\beta,y)$

is $O(1)$-subgaussian. We will apply Theorem 2.4 to the mean zero process
$(\Sigma_{y})_{y\in Q}$ with the pseudometric
$D_{K}(x,y)=\|\phi(x)-\phi(y)\|_{\mathcal{H}_{K}}$, the kernel distance
defined in Section 1.2. To see why $D_{K}$ satisfies the condition of Theorem
2.4, note that for any $y,q\in Q$,

$\mathrm{Var}[\Sigma_{y}-\Sigma_{q}]^{1/2}=\mathbb{E}[\big{\langle}\Sigma,\phi(y)-\phi(q)\big{\rangle}^{2}]^{1/2}\lesssim\|\phi(y)-\phi(q)\|_{\mathcal{H}_{K}}=D_{K}(y,q).$

Thus by Theorem 2.5,

$\mathbb{E}\ \mathrm{disc}_{K|_{Q}}(X)=\mathbb{E}\sup_{y\in
Q}|\Sigma_{y}|\lesssim\int_{0}^{\mathrm{diam}(D_{K})}\sqrt{\log\mathcal{N}(Q,D_{K},r)}\
\mathrm{d}r+\|\Sigma_{y_{0}}\|_{\psi_{2}}$ (2)

for any fixed $y_{0}\in Q$. Here $\|\Sigma_{y_{0}}\|_{\psi_{2}}\leq O(1)$, and
so we may ignore this lower order term. To estimate $\mathcal{N}(Q,D_{K},r)$,
we use conditions (ii) and (iii) to note that

$D_{K}(q,y)=\sqrt{2-2\kappa(\alpha\|q-y\|_{2})}\leq r\ \ \iff\ \
\|q-y\|_{2}\leq\frac{1}{\alpha}\kappa^{-1}\left(\frac{2-r^{2}}{2}\right),$

where we use that $\kappa$ is strictly decreasing. From this calculation we
conclude that

$\mathcal{N}(Q,D_{K},r)=\mathcal{N}\left(Q,\|\cdot\|_{2},\frac{1}{\alpha}\kappa^{-1}\left(\frac{2-r^{2}}{2}\right)\right).$

Taking $c:=\frac{1}{\alpha}\kappa^{-1}\left(\frac{2-r^{2}}{2}\right)$ for a
moment, we can bound the quantity on the right using Lemma 2.7:

$\displaystyle\begin{split}\mathcal{N}\left(Q,\|\cdot\|_{2},c\right)&=N(Q,\
cB_{2}^{d})\\\ &\leq N(RB_{2}^{d},cB_{2}^{d})\\\ &\leq
2^{d}\frac{\textrm{Vol}_{d}((R+\frac{c}{2})B_{2}^{d})}{\textrm{Vol}_{d}(cB_{2}^{d})}\\\
&\leq\left(\frac{4R}{c}\right)^{d},\end{split}$ (3)

where we use Lemma 2.7 and $c\leq R$ (if $c>R$ then the covering number is
trivially 1). Using this bound in (2), we find

$\displaystyle\begin{split}\mathbb{E}\
\mathrm{disc}_{K|_{Q}}(X)&\lesssim\int_{0}^{\mathrm{diam}(D_{K})}\sqrt{\log\left[\left(\frac{4R\alpha}{{\kappa^{-1}\left(\frac{2-r^{2}}{2}\right)}}\right)^{d}\right]}\
\mathrm{d}r\\\
&\lesssim\sqrt{d}\int_{0}^{\mathrm{diam}(D_{K})}\sqrt{\log\left[\frac{4R\alpha}{{\kappa^{-1}\left(\frac{2-r^{2}}{2}\right)}}\right]}\
\mathrm{d}r\\\
&\lesssim\sqrt{d\log(2R\alpha)}+\sqrt{d}\int_{0}^{\mathrm{diam}(D_{K})}\sqrt{\log\left[\frac{1}{{\kappa^{-1}\left(\frac{2-r^{2}}{2}\right)}}\right]}\
\mathrm{d}r\\\ &\lesssim\sqrt{d\log(2R\alpha)}+O(\sqrt{d}).\end{split}$ (4)

To justify these calculations, note that in the event that the quantity inside
the radical is negative, it means that

$4R\alpha\leq\kappa^{-1}\Big{(}\frac{2-r^{2}}{2}\Big{)},$

and hence by (3) we know that $\mathcal{N}(Q,D_{K},r)=2^{O(d)}$. As
$\mathrm{diam}(D_{K})\leq 2$, the domain of $r$ values for which this occurs
has length $\leq 2$, so we can simply restrict the domain to this point while
losing at most an additive $O(\sqrt{d})$. Note that as $\kappa$ is assumed
strictly decreasing and continuous,
$\kappa^{-1}\big{(}\frac{2-r^{2}}{2}\big{)}$ is an increasing, continuous
function of $r$. Thus in particular
$\kappa^{-1}\big{(}\frac{2-r^{2}}{2}\big{)}\rightarrow 0$ as $r\rightarrow 0$,
based on our assumption that $K(x,x)=1$ for all $x\in\mathbb{R}^{d}$. Finally,
by Lemma 1.7,

$\mathbb{E}\ \mathrm{disc}_{K}(X)\leq\mathbb{E}\
\mathrm{disc}_{K|_{Q}}(X)+O(1)\lesssim\sqrt{d\log(2\alpha R)}.\qed$

Next we prove Theorem 1.9, which gives improved bounds independent of the
geometry of the data set $X$.

###### Proof of Theorem 1.9.

Fix a kernel $K$ satisfying conditions (i)-(iv) with impact radius $r_{K}$,
and let $X\subseteq\mathbb{R}^{d}$. Fix the associated query space $Q$ as
given by Definition 1.6. As we assume that $K$ is positive definite and
satisfies $K(x,x)=1$ for all $x\in Q$, there exists a map
$\phi:\mathbb{R}^{d}\rightarrow\mathcal{H}_{K}$, where $\mathcal{H}_{K}$ is a
RKHS such that $K(x,y)=\langle\phi(x),\phi(y)\rangle$ for all
$x,y\in\mathbb{R}^{d}$, and $\|\phi(x)\|_{\mathcal{H}_{K}}=1$ for all
$x\in\mathbb{R}^{d}$. We first find a maximal set of points
$q_{1},\ldots,q_{m}\in Q$ such that for any $\|q_{i}-q_{j}\|_{2}\geq r_{K}$
for any $i,j\in[m]$. We then partition the space $Q$ into disjoint cells

$Q:=R_{1}\dot{\cup}\cdots\dot{\cup}R_{m}$

so that

$R_{i}\subseteq q_{i}+r_{K}B_{2}^{d}$ (5)

for each $i\in[m]$. These cells also partition the set $X$ into smaller sets
$X_{i}:=X\cap R_{i}$. We begin with the set $X_{1}$; because the conditions in
Theorems 1.8 and 1.9 are the same, by identical arguments to the proof of
Theorem 1.8 we obtain a random variable $\Sigma^{1}:=\sum_{x\in
X_{1}}\beta^{(1)}(x)\phi(x)$, where $\beta^{(1)}\sim\\{\pm 1\\}^{X_{1}}$ is
drawn according to the Gram-Schmidt walk. By Theorem 2.1, $\Sigma^{1}$ is
$O(1)$-subgaussian, so in particular, for any $y\in Q$, as
$\|\phi(y)\|_{\mathcal{H}_{K}}=1$, the random variable

$\Sigma^{1}(y):=\Big{\langle}\phi(y),\sum_{x\in
X_{1}}\beta^{(1)}(x)\cdot\phi(x)\Big{\rangle}$

is also $O(1)$-subgaussian.

For each $j\in[m]$, we now have the collection of (mean zero) random variables
$\\{\Sigma^{j}(y):\ y\in R_{j}\\}$. We fix $j\in[m]$; then by our assumption
in (5), our query space $R_{j}$ has volume at most
$\mathrm{Vol}_{d}(r_{K}B_{2}^{d})$. By a calculation analogous to that in (3),
we have that for all $r>0$,

$\mathcal{N}(R_{j},D_{K},r)\leq\max\Big{\\{}\Big{(}\frac{4\alpha
r_{K}}{r}\Big{)}^{d},1\Big{\\}}.$ (6)

Here we note that because of our assumption that
$K(x,y)=\kappa(\alpha\|x-y\|_{2})$ and the definition of $r_{K}(n)$, we have
for $x,y$ with $\|x-y\|_{2}=r_{K}(n)$,

$K(x,y)=\kappa(\alpha r_{K}(n))\leq 1/n\ \implies\ \alpha
r_{K}(n)\leq\kappa^{-1}(1/n)\ \implies\
r_{K}(n)\leq\frac{1}{\alpha}\kappa^{-1}(1/n).$ (7)

Thus the quantity $\alpha r_{K}$ appearing in (6) can actually be bounded by a
term independent of $\alpha$. Note that by assumption (iii), $\kappa^{-1}$ is
a decreasing function. Thus by the same analysis in the proof of Theorem 1.9,
we have

$\mathrm{disc}_{K|_{R_{j}}}(X_{1})\lesssim\int_{0}^{\mathrm{diam}(D_{K}|_{R_{j}})}\sqrt{\log\mathcal{N}(R_{j},D_{K},r)\
}\mathrm{d}r=O(\sqrt{d\log\kappa^{-1}(1/n)}).$

Applying Theorem 2.6 with $u:=C_{0}\sqrt{d}$ yields that

$\mathbb{P}\big{\\{}\sup_{y\in R_{j}}\ |\Sigma^{1}(y)|\geq C\cdot
C_{0}\sqrt{d}\big{\\}}\leq 2e^{-dC_{0}^{2}},$ (8)

where $C$ is the constant from Theorem 2.6 and $C_{0}>0$. Moreover, by
standard packing arguments, this probability is in fact $0$ for all but at
most $2^{O(d)}$ choices of $j\in[m]$, as any $R_{j}$ not adjacent to (or the
same as) $R_{1}$ will have distance $\Omega(r_{K})$ from any point $x\in
X_{1}$, hence by the definition of the impact radius $r_{K}$ and the bound in
(7), for any such $R_{j}$ the above probability is $0$. We apply the union
bound over the $2^{O(d)}$ cells where (8) could fail and obtain that for
$C_{0}$ large enough,

$\displaystyle\begin{split}\mathbb{P}\Big{\\{}\forall j\in[m]:\ \sup_{y\in
R_{j}}\ |\Sigma^{1}(y)|\geq C\cdot C_{0}\sqrt{d\log
r_{K}}\Big{\\}}&=\mathbb{P}\Big{\\{}\sup_{y\in Q}|\Sigma^{1}(y)|\geq
C_{0}\sqrt{d\log r_{K}}\Big{\\}}\\\ &\leq 2^{O(d)}\cdot
2(\kappa^{-1}(1/n))^{-C_{0}^{2}d}<1.\end{split}$ (9)

Thus with positive probability, $\mathrm{disc}_{K}(X_{1})\leq C\cdot
C_{0}\sqrt{d\log\kappa^{-1}(1/n)}$. We then fix such an outcome and repeat
this construction independently for $R_{2},...,R_{m}$, at each step repeating
the Gram-Schmidt algorithm until we get the outcome as in (9). After repeating
this construction $m$ times, we have a choice of signs
$\beta=(\beta^{(1)},...,\beta^{(m)})\in\\{\pm 1\\}^{X}$ so that by the
triangle inequality

$\mathrm{disc}_{K}(X)\leq\sum_{i\in[m]}\mathrm{disc}_{K}(X_{i}).$ (10)

However, for our purpose this bound is too weak. But because the function
$K=\kappa(\|x-y\|_{2})$ is symmetric in $x$ and $y$, by the same packing
argument we made above, we know that for each fixed point $y\in Q$, only
$2^{O(d)}$ terms in the summand in (10) can contribute a discrepancy larger
than $O(1)$. Thus we conclude that

$\mathrm{disc}_{K}(X)\leq 2^{O(d)}\sqrt{d\log\kappa^{-1}(1/n)}.$

As $X\subseteq\mathbb{R}^{d}$ was arbitrary, the bound follows. ∎

##  4\. Applications to Specific Kernels of Interest

In this section we highlight the applications of Theorems 1.8 and 1.9 to
several kernels of interest in machine learning.

###  4.1. The Gaussian and Laplacian Kernels

The Gaussian and Laplacian kernels are two of the most important and most
commonly used kernels in machine learning [22]. The Gaussian kernel is defined
by

$K_{G}:\ \mathbb{R}^{d}\times\mathbb{R}^{d}\rightarrow\mathbb{R}\ \ \ \
K_{G}(x,y)=\exp(-\alpha^{2}\|x-y\|_{2}^{2}),$

and the Laplacian kernel is defined by

$K_{L}:\ \mathbb{R}^{d}\times\mathbb{R}^{d}\rightarrow\mathbb{R}\ \ \
K_{L}(x,y)=\exp(-\alpha\|x-y\|_{2}),$

where again $1/\alpha>0$ is the bandwidth parameter of the kernels. Currently
the best known bound for both the Gaussian and the Laplacian kernels in
arbitrary dimension $d$ is $O(\sqrt{d\log n})$, and because these bounds rely
on taking $1/n$-nets of the query space, even if the given data set $X$
satisfies nice properties such as boundedness, the $\sqrt{\log n}$ term
remains. However, Theorem 1.8 allows us to give significant improvements on
this $O(\sqrt{d\log n})$ bound given such a data set.

######  Corollary 4.1.

For the Gaussian kernel $K_{G}$ with any bandwidth parameter $\alpha>0$ and
any data set $X\subseteq RB_{2}^{d}$ for any fixed constant $R>0$, we have

$\mathrm{disc}_{K_{G}}(X)=O(\sqrt{d\log\log n}).$

In particular, one can find (in randomized polynomial time) a coreset for $X$
of size

$O\left(\frac{\sqrt{d}}{\varepsilon}\sqrt{\log\log\frac{1}{\varepsilon}}\right).$

###### Proof.

We first check the conditions of Theorem 1.8 for the Gaussian kernel. It is
well-known that $K_{G}$ is positive definite, and clearly $K_{G}(x,x)=e^{0}=1$
for any $x\in\mathbb{R}^{d}$. Taking $\kappa_{G}(z):=e^{-z^{2}}$ gives us
$K_{G}(x,y)=\kappa_{G}(\alpha\|x-y\|_{2})$, and $\kappa$ is strictly
decreasing on $\mathbb{R}^{+}$; finally,

$\sqrt{-\log\big{[}\kappa^{-1}\big{(}\tfrac{2-r^{2}}{2}\big{)}\big{]}}\lesssim\sqrt{\log{\left[\frac{1}{\log\big{(}\tfrac{2}{2-r^{2}}\big{)}}\right]}}$

is dominated by $O(1/r^{2})$ for $r\in\mathbb{R}^{+}$, hence is integrable on
its domain. Finally, we note that the query space $Q$ is given by

$Q:=\bigcup_{x\in X}B_{2}^{d}(x,r_{K_{G}})\subseteq O(r_{K_{G}})B_{2}^{d},$

as we assume that $\mathrm{radius}(X)=O(1)$. Thus Theorem 1.8 yields

$\mathrm{disc}_{K_{G}}(X)\lesssim O(\sqrt{d\log R\alpha})=O(\sqrt{d\log\log
n})$

by the fact that $R=O(r_{K})$ and the same observation as in the proof of
Theorem 1.9 that

$\alpha r_{K_{G}}\leq\kappa_{G}^{-1}(1/n)=\sqrt{\log n}.$

To see the bound on the size of a minimal coreset, we will apply the “halving
trick” shown in Section 1.1. The above argument shows a bound of
$f(n)=O(\sqrt{d\log\log n})$ on the kernel discrepancy; iterating the
discrepancy calculation $t$ times and removing the points colored $-1$ at each
step, we obtain the following bound after $t$ iterations:

$\|\mathrm{KDE}_{X}-\mathrm{KDE}_{X_{t}}\|_{\infty}\lesssim\sum_{s\in[t]}\frac{2^{s-1}}{n}\sqrt{d\log\log\tfrac{n}{2^{s-1}}}.$

This sum is dominated by the $t^{th}$ term, so we can repeat this calculation
until the size of the remaining set of data points $m:=n/2^{s-1}$ satisfies

$m\sqrt{d\log\log m}=\varepsilon,$

which occurs for
$m=O\big{(}\frac{\sqrt{d}}{\varepsilon}\sqrt{\log\log\frac{1}{\varepsilon}}\big{)}$,
yielding the bound. ∎

This exact technique can always be used to provide coreset bounds, assuming
that the term $f(n)$ grows significantly slowly with $n$, which it always will
for our applications. Thus we will not repeat this calculation for the proofs
of the remaining theorems. Note that an identical argument for the discrepancy
yields the proof of Corollary 1.1 stated in Section 1.4. However, in general
if the diameter of the set $X$ depends on the number of data points, one has
to be more careful to obtain bounds on the coreset complexity, as this
dependence may change as we remove data points.

The following theorem follows from essentially identical arguments to those in
the previous proof, noting that the Laplacian kernel can be written as
$K_{L}(x,y)=\kappa_{L}(\alpha\|x-y\|_{2})$, with $\kappa_{L}(z)=e^{-z}$.

######  Corollary 4.2.

For the Laplacian kernel $K_{L}$ with any $\alpha>0$ and any data set
$X\subseteq RB_{2}^{d}$ for any fixed constant $R>0$ we have

$\mathrm{disc}_{K_{L}}(X)=O(\sqrt{d\log\log n}).$

In particular, one can find (in randomized polynomial time) a coreset for $X$
of size

$O\left(\frac{\sqrt{d}}{\varepsilon}\sqrt{\log\log\frac{1}{\varepsilon}}\right).$

Thus in the interest of applications, we can invoke useful properties of the
data set $X$ in order to obtain better bounds, something that was not possible
due to the discretization technique used in [19]. Karnin and Liberty [14]
provide bounds assuming that the entire query space lies in a bounded region
(for a particular constant depending on the kernel), but our assumption is
much weaker: we are only interested in the geometry of the data set, not the
query space.

In the case when our data is sufficiently low dimensional that a $2^{O(d)}$
factor is not prohibitively large, i.e. for $d$ constant, Theorem 1.9 yields
the following improvement on the current best known bound for the Laplacian
kernel [19].

######  Corollary 4.3.

For the Laplacian kernel $K_{L}$ with any $\alpha>0$, we have

$\mathrm{disc}_{K_{L}}(n)=2^{O(d)}\sqrt{\log\log n}.$

In particular, given any data set $X\subseteq\mathbb{R}^{d}$, we can find (in
randomized polynomial time) a coreset of size

$\frac{2^{O(d)}}{\varepsilon}\sqrt{\log\log\frac{1}{\varepsilon}}.$

###### Proof.

The verification that the Laplacian kernel satisfies conditions (i)-(iv) of
Theorem 1.9 is essentially identical to showing that the Gaussian kernel
satisfies these properties, so we refer back to the proof of Corollary 4.1. As
mentioned previously, the Laplacian kernel can be written as
$K_{L}(x,y)=\kappa_{L}(\alpha\|x-y\|_{2})$, where $\kappa_{L}(z)=e^{-z}$, and
applying Theorem 1.9 then yields the bound above. ∎

We note that the same bound follows for the Gaussian kernel as well, though a
recent paper of Tai [25] gives a bound of $O(1)$ on the discrepancy of the
Gaussian kernel for $d$ constant. The technique Tai used for the Gaussian does
not appear to generalize to other kernels, whereas our technique applies to a
broader class of kernels that also includes the Laplacian kernel.

###  4.2. The Exponential and the Hellinger kernel

We can also obtain improved bounds for the exponential kernel

$K_{e}:S^{d}\times S^{d}\rightarrow\mathbb{R}^{d},\ \ \
K_{e}(x,y)=\exp(-\alpha(1-\langle x,y\rangle)),$

and the Hellinger kernel

$K_{H}:\Delta_{d}\times\Delta_{d}\rightarrow\mathbb{R},\ \ \ \
K_{H}(x,y)=\exp\Big{(}-\alpha\sum_{i\in[d]}(\sqrt{x_{i}}-\sqrt{y_{i}})^{2}\Big{)}$

by applying Theorem 1.8.

###### Proof of Theorem 1.11.

First we note that $x,y\in S^{d}$, hence in particular
$\|x\|_{2}=\|y\|_{2}=1$, so we can re-write the exponential kernel as

$K_{e}(x,y)=\exp\Big{(}-\frac{\alpha}{2}\|x-y\|_{2}^{2}\Big{)}=K_{G}|_{S^{d}},$

from which we see that $K_{e}$ satisfies the conditions of Theorem 1.8. As the
query space is $Q=S^{d}\subset B_{2}^{d}$, we can apply Theorem 1.8 with
$R=1$. ∎

We now argue that the same bound applies to the Hellinger kernel.

######  Lemma 4.1.

The Hellinger kernel $K_{H}$ has discrepancy at most that of the exponential
kernel $K_{e}$, i.e.

$\mathrm{disc}_{K_{H}}(n)\leq\mathrm{disc}_{K_{e}}(n).$

###### Proof of Lemma 4.1.

Given a data set $X\subseteq\Delta_{d}$ of size $n$, we make the
transformation

$f:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d},\ \ \
(x_{1},\ldots,x_{d})\rightarrow(\sqrt{x_{1}},\ldots,\sqrt{x_{d}}).$

Here we make two observations: first, $f$ maps $\Delta^{d}$ into $S^{d}$, and
second, for $x,y\in S^{d}$, and

$K_{H}(x,y)=\exp\Big{(}-\alpha\sum_{i\in[d]}(\sqrt{x_{i}}-\sqrt{y_{i}})^{2}\Big{)}=\exp(-\alpha\|f(x)-f(y)\|_{2}^{2})=K_{e}(f(x),f(y)).$

By the first observation, we can apply our bound on the exponential kernel
discrepancy of the set $\\{f(x):\ x\in X\\}\subseteq S^{d}$ to find signs
$\beta\in\\{\pm 1\\}^{X}$ so that

$\displaystyle\sup_{y\in S^{d}}\ \Big{|}\sum_{x\in
X}\beta(x)K_{e}(f(x),y)\Big{|}$ $\displaystyle=\sup_{z\in\Delta^{d}}\
\Big{|}\sum_{x\in X}\beta(x)K_{e}(f(x),f(z))\Big{|}$
$\displaystyle=\sup_{z\in\Delta^{d}}\Big{|}\sum_{x\in
X}\beta(x)K_{H}(x,z)\Big{|}$ $\displaystyle=\mathrm{disc}_{K_{H}}(X)$

satisfies the bound of Theorem 1.11. Thus we conclude that

$\mathrm{disc}_{K_{H}}(X)\leq\mathrm{disc}_{K_{e}}(X),$

and as $X$ was an arbitrary data set, the lemma follows.

∎

Theorem 1.12 then follows immediately from Theorem 1.11 and Lemma 4.1.

##  5\. The Jensen-Shannon kernel

Finally, we prove the following bound for a specific kernel that does not
directly satisfy the conditions of Theorems 1.8 and 1.9: the Jensen-Shannon
(JS) Kernel, defined by

$K_{JS}:\Delta_{d}\times\Delta_{d}\rightarrow\mathbb{R}\ \ \ \
K_{JS}(x,y)=\exp\left[-\alpha\left(H\left(\frac{x+y}{2}\right)-\frac{H(x)+H(y)}{2}\right)\right],$

where $H(z)=-\sum_{i\in[d]}z_{i}\ln z_{i}$ is the Shannon entropy function.
Note that the quantity in the exponent of the JS Kernel,
$H\left(\frac{x+y}{2}\right)-\frac{H(x)+H(y)}{2}$, is precisely the Jensen gap
for the Shannon entropy function (hence the name Jensen-Shannon kernel).

The Jensen-Shannon kernel, as well as the Hellinger kernel introduced in
Section 4, are commonly used in information theory, as they represent
similarity between histograms (i.e. the data points are discrete probability
distributions over $d$ variables). One example from text analysis [19] is
encoding with each data point $X$, corresponding to a text, the probabilities
of $d$ certain words appearing in that text. Although the JS kernel does not
satisfy many of the conditions of our theorems, a similar proof strategy
yields Theorem 1.10.

To prove this result, we will need the following lemmas bounding the one-
dimensional entropy function, which we will denote by
$h(x):=x\ln(\frac{1}{x})=-x\ln(x)$.

######  Lemma 5.1.

For $a,\delta\geq 0$ one has $|2h(a+\delta)-(h(a)+h(a+2\delta))|\leq 3\delta$.

###### Proof.

By continuity of $h$ it suffices to prove the inequality for the case of
$a>0$. We have

$\displaystyle|2h(a+\delta)-h(a)-h(a+2\delta)|$ $\displaystyle=$
$\displaystyle|2(a+\delta)\ln(a+\delta)-a\ln(a)-(a+2\delta)\ln(a+2\delta)|$
$\displaystyle=$
$\displaystyle\Big{|}2(a+\delta)\cdot\Big{(}\ln(a)+\ln\Big{(}1+\frac{\delta}{a}\Big{)}\Big{)}-a\ln(a)-(a+2\delta)\cdot\Big{(}\ln(a)+\ln\Big{(}1+\frac{2\delta}{a}\Big{)}\Big{)}\Big{|}$
$\displaystyle=$
$\displaystyle\Big{|}2(a+\delta)\ln\Big{(}1+\frac{\delta}{a}\Big{)}-(a+2\delta)\ln\Big{(}1+\frac{2\delta}{a}\Big{)}\Big{|}$
$\displaystyle\stackrel{{\scriptstyle\textrm{triangle ineq.}}}{{\leq}}$
$\displaystyle
a\cdot\underbrace{\Big{|}2\ln\Big{(}1+\frac{\delta}{a}\Big{)}-\ln\Big{(}1+\frac{2\delta}{a}\Big{)}\Big{|}}_{\leq\delta/a}+2\delta\cdot\underbrace{\Big{|}\ln\Big{(}1+\frac{\delta}{a}\Big{)}-\ln\Big{(}1+\frac{2\delta}{a}\Big{)}\Big{|}}_{\leq
1}\leq 3\delta$

Here one can verify that $|2\ln(1+z)-\ln(1+2z)|\leq z$ for all $z\geq 0$ which
we use to bound the left term. To bound the right term we use that
$|\ln(1+z)-\ln(1+2z)|\leq 1$ for all $z\geq 0$. ∎

######  Lemma 5.2.

For $a,b\geq 0$ one has
$|h(\frac{a+b}{2})-\frac{h(a)+h(b)}{2}|\leq\frac{3}{4}|a-b|$.

###### Proof.

Suppose $b\geq a$. Applying Lemma 5.1 with $a$ and $\delta:=\frac{b-a}{2}$
gives

$\Big{|}2h\Big{(}\frac{a+b}{2}\Big{)}-(h(a)+h(b))\Big{|}\leq
3\cdot\frac{b-a}{2}=\tfrac{3}{2}|a-b|.$

The claim follows after dividing both sides by 2. ∎

###### Proof of Theorem 1.10.

As the JS Kernel is positive definite, there exists a map
$\phi:\Delta^{d}\rightarrow\mathcal{H}_{K_{JS}}$, where $\mathcal{H}_{K_{JS}}$
is a RKHS for $K_{JS}$, i.e. for any choice of $x,y\in\Delta_{d}$,
$K_{JS}(x,y)=\langle\phi(x),\phi(y)\rangle_{\mathcal{H}_{K_{JS}}}$. Then as
$\|\phi(x)\|_{\mathcal{H}_{K_{JS}}}=e^{0}=1$ for any choice of
$x\in\Delta^{d}$, we can apply the Gram-Schmidt walk to the collection of
vectors $\\{\phi(x)\\}_{x\in\Delta_{d}}$ exactly as in the proofs of Theorems
1.8 and 1.9 to obtain a distribution $\mathcal{D}$ over $\\{\pm 1\\}^{X}$ and
a corresponding family of $O(1)$-subgaussian random variables

$\Sigma_{y}:=\mathrm{disc}_{K_{JS}}(X,\beta,y),\ \ \ y\in\Delta_{d},\
\beta\sim\mathcal{D}.$

Then applying Theorem 2.4 to this collection of random variables with the
pseudometric

$D_{K_{JS}}(x,y)=\|\phi(x)-\phi(y)\|_{\mathcal{H}_{K_{JS}}}=\sqrt{2-2K_{JS}(x,y)},$

we find that

$\mathbb{E}\
\mathrm{disc}_{K_{JS}}(X)\lesssim\int_{0}^{\mathrm{diam}(D_{K_{JS}})}\sqrt{\log\mathcal{N}(\Delta_{d},D_{K_{JS}},r)}\
\mathrm{d}r.$ (11)

We focus on bounding the term $\mathcal{N}(\Delta_{d},D_{K_{JS}},r)$, for
which we will use Lemma 5.2. First, note that for
$x=(x_{1},\ldots,x_{d})\in\mathbb{R}^{d}$, breaking the $d$-dimensional
entropy function $H$ down component-wise as $H(x)=\sum_{i\in[d]}h(x_{i})$:

$D_{K_{JS}}(x,y)\leq r\ \ \iff\ \
\sum_{i\in[d]}\left(h\left(\frac{x_{i}+y_{i}}{2}\right)-\frac{h(x_{i})+h(y_{i})}{2}\right)\leq\frac{1}{\alpha}\log\big{(}\tfrac{2}{2-r^{2}}\big{)}.$
(12)

By Lemma 5.2, we know that for each $i\in[d]$,

$h\left(\frac{x_{i}+y_{i}}{2}\right)-\frac{h(x_{i})+h(y_{i})}{2}\leq|x_{i}-y_{i}|,$

hence

$\sum_{i\in[d]}\left(h\left(\frac{x_{i}+y_{i}}{2}\right)-\frac{h(x_{i})+h(y_{i})}{2}\right)\leq\sum_{i\in[d]}|x_{i}-y_{i}|=\|x-y\|_{1}.$

In particular, by (12),
$\|x-y\|_{1}\leq\frac{1}{\alpha}\log\big{(}\tfrac{2}{2-r^{2}}\big{)}=:c$
implies that $D_{K_{JS}}(x,y)\leq r$, so we have the bound

$\mathcal{N}(\Delta_{d},D_{K_{JS}},r)\leq\mathcal{N}(\Delta_{d},\|\cdot\|_{1},c)\leq
N(B_{1}^{d},cB_{1}^{d})\leq\Big{(}1+\frac{2}{c}\Big{)}^{d}\leq\Big{(}\frac{3}{c}\Big{)}^{d}$

for $c\leq 1$ using Lemma 2.8 (and if $c>1$, the covering number is 1 anyway).
Returning to (11), we conclude

$\mathbb{E}\
\mathrm{disc}_{K_{JS}}(X)\lesssim\int_{0}^{\mathrm{diam}(D_{K})}\sqrt{\log\left[\left(\frac{3\alpha}{\log\tfrac{2}{2-r^{2}}}\right)^{d}\right]}\
\mathrm{d}r\lesssim\sqrt{d\log(2\max\\{1,\alpha\\})},$

by the same argument as in the proofs of Theorems 1.8 and 1.9. ∎

##  6\. Conclusions and Potential Future Questions

In this paper we give improved bounds of order
$O(\frac{\sqrt{d}}{\varepsilon}\sqrt{\log\log\tfrac{1}{\varepsilon}})$ on the
coreset complexity of the Gaussian and Laplacian kernels (as well as other
kernels satisfying sufficiently nice properties) in the case that the data set
of interest has $O(1)$ diameter. We also give improved bounds of order
$O(\frac{1}{\varepsilon}\sqrt{\log\log(1/\varepsilon)})$ for the Laplacian
kernel in the case that the dimension $d$ is constant, extending a recent
result of Tai for the Gaussian kernel [25] with a
$\sqrt{\log\log(1/\varepsilon)}$ loss. Finally, we provide the best known
bounds of $O(\frac{\sqrt{d}}{\varepsilon}\sqrt{\log(2\max\\{\alpha,1\\})})$
for the Jensen-Shannon, exponential, and Hellinger kernels, in particular
significantly improving the dependence on the bandwidth parameter $1/\alpha$
for the exponential kernel. To conclude the paper, we echo two remaining open
question of interest given also in [19, 25] respectively. First, it would be
interesting to prove (or disprove) an upper bound of $O(\sqrt{d}/\varepsilon)$
on the coreset complexity of Lipschitz positive definite kernels with nice
decay properties to match the bound in [19]. Second, it would be interesting
to extend our $O(\sqrt{\log\log n})$ bound from Theorem 1.9 in constant
dimension to either an even broader class of kernels, or even more
interestingly, to drop the $\sqrt{\log\log n}$ dependence entirely, as Tai is
able to do in the special case of the Gaussian. Our analytic method allows us
to move one step closer to either of these results by removing the extra
factor of $\sqrt{\log n}$ introduced by discretizing the query space.

## References

  * [1] N. Aronszajn.  Theory of reproducing kernels.  Transactions of the American Mathematical Society, 68:337–404, 1950\.
  * [2] Shiri Artstein-Avidan, Apostolos Giannopoulos, and Vitali D Milman.  Asymptotic Geometric Analysis, Part I.  Mathematical surveys and monographs. American Mathematical Society, 2015\.  Includes bibliographical references and indexes.
  * [3] Francis Bach, Simon Lacoste-Julien, and Guillaume Obozinski.  On the equivalence between herding and conditional gradient algorithms.  In Proceedings of the 29th International Coference on International Conference on Machine Learning, ICML’12, page 1355–1362, Madison, WI, USA, 2012. Omnipress.
  * [4] Wojciech Banaszczyk.  Balancing vectors and Gaussian measures of $n$-dimensional convex bodies.  Random Structures & Algorithms, 12(4):351–360, 1998.
  * [5] Nikhil Bansal, Daniel Dadush, Shashwat Garg, and Shachar Lovett.  The Gram-Schmidt walk: A Cure for the Banaszczyk Blues.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, page 587–597, New York, NY, USA, 2018. Association for Computing Machinery.
  * [6] Jon Louis Bentley and James B Saxe.  Decomposable searching problems i. static-to-dynamic transformation.  Journal of Algorithms, 1(4):301–358, 1980.
  * [7] Bernard Chazelle and Jiri Matousek.  On linear-time deterministic algorithms for optimization problems in fixed dimension.  Journal of Algorithms, 21(3):579–597, 1996.
  * [8] Yutian Chen, Max Welling, and Alex Smola.  Super-samples from kernel herding.  In Proceedings of the Twenty-Sixth Conference on Uncertainty in Artificial Intelligence, UAI’10, page 109–116, Arlington, Virginia, USA, 2010\. AUAI Press.
  * [9] Efren Cruz and Clayton Scott.  Sparse approximation of a kernel mean.  IEEE Transactions on Signal Processing, PP, 03 2015.
  * [10] Brittany Terese Fasy, Fabrizio Lecci, Alessandro Rinaldo, Larry Wasserman, Sivaraman Balakrishnan, and Aarti Singh.  Confidence sets for persistence diagrams.  The Annals of Statistics, 42(6):2301 – 2339, 2014.
  * [11] Nick Harvey and Samira Samadi.  Near-optimal herding.  In Maria Florina Balcan, Vitaly Feldman, and Csaba Szepesvári, editors, Proceedings of The 27th Conference on Learning Theory, volume 35 of Proceedings of Machine Learning Research, pages 1165–1182, Barcelona, Spain, 13–15 Jun 2014. PMLR.
  * [12] Sarang Joshi, Raj Varma Kommaraji, Jeff M. Phillips, and Suresh Venkatasubramanian.  Comparing distributions and shapes using the kernel distance.  In Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry, SoCG ’11, page 47–56, New York, NY, USA, 2011. Association for Computing Machinery.
  * [13] Sarang Joshi, Raj Varma Kommaraji, Jeff M. Phillips, and Suresh Venkatasubramanian.  Comparing distributions and shapes using the kernel distance.  In Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry, SoCG ’11, page 47–56, New York, NY, USA, 2011. Association for Computing Machinery.
  * [14] Zohar Karnin and Edo Liberty.  Discrepancy, coresets, and sketches in machine learning.  In Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 1975–1993. PMLR, 25–28 Jun 2019.
  * [15] Simon Lacoste-Julien, Fredrik Lindsten, and Francis R. Bach.  Sequential kernel herding: Frank-wolfe optimization for particle filtering.  ArXiv, abs/1501.02056, 2015.
  * [16] David Lopez-Paz, Krikamol Muandet, Bernhard Schölkopf, and Ilya Tolstikhin.  Towards a learning theory of cause-effect inference.  In Proceedings of the 32nd International Conference on International Conference on Machine Learning - Volume 37, ICML’15, page 1452–1461. JMLR.org, 2015.
  * [17] Jiri Matousek.  Geometric discrepancy: An illustrated guide, volume 18.  Springer Science & Business Media, 1999.
  * [18] Krikamol Muandet, Kenji Fukumizu, Bharath Sriperumbudur, and Bernhard Schölkopf.  2017\.
  * [19] Jeff Phillips and Wai Tai.  Near-optimal coresets of kernel density estimates.  Discrete and Computational Geometry, 63, 06 2020.
  * [20] Jeff M. Phillips.  Algorithms for $\varepsilon$-approximations of terrains.  In Proceedings of the 35th International Colloquium on Automata, Languages and Programming - Volume Part I, ICALP ’08, page 447–458, Berlin, Heidelberg, 2008. Springer-Verlag.
  * [21] Jeff M. Phillips.  $\varepsilon$-samples for Kernels.  In Proceedings of the Twenty-Fourth Annual Symposium on Discrete Algorithms, pages 1622–1632. SIAM, 2013.
  * [22] D.W. Scott.  Multivariate Density Estimation: Theory, Practice, and Visualization.  A Wiley-interscience publication. Wiley, 1992.
  * [23] Bernard W Silverman.  Density estimation for statistics and data analysis.  Routledge, 2018.
  * [24] Le Song, Xinhua Zhang, Alex Smola, Arthur Gretton, and Bernhard Schölkopf.  Tailoring density estimation via reproducing kernel moment matching.  In Proceedings of the 25th International Conference on Machine Learning, ICML ’08, page 992–999, New York, NY, USA, 2008. Association for Computing Machinery.
  * [25] Wai Ming Tai.  Optimal Coreset for Gaussian Kernel Density Estimation.  In Xavier Goaoc and Michael Kerber, editors, 38th International Symposium on Computational Geometry (SoCG 2022), volume 224 of Leibniz International Proceedings in Informatics (LIPIcs), pages 63:1–63:15, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
  * [26] A.B. Tsybakov.  Introduction to Nonparametric Estimation.  Springer Series in Statistics. Springer New York, 2008.
  * [27] Roman Vershynin.  High-Dimensional Probability: An Introduction with Applications in Data Science.  Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018.