# Early evolution of spin direction in dark matter halos and the effect of the
surrounding large-scale tidal<EMAIL_ADDRESS>work conducted
at Facultad de Matemática, Astronomía, Física y Computación, Universidad
Nacional de Córdoba, Córdoba, Argentina.222PhD Thesis directed by Manuel
Merchán; PhD Degree awarded 2023 July 31.

Pablo López Observatorio Astronómico de Córdoba, Universidad Nacional de
Córdoba (UNC), Francisco N. Laprida 854, Córdoba, Argentina  Instituto de
Astronomía Teórica y Experimental, CONICET-UNC, Laprida 922, Córdoba,
Argentina<EMAIL_ADDRESS>
###### Abstract

It is usually assumed that the angular momentum (AM) of dark matter halos
arises during the linear stages of structure formation, as a consequence of
the coupling between the proto-haloes’ shape and the tidal field produced by
their surrounding density perturbations. This approach, known as linear tidal
torque theory (TTT), has been shown to make fairly good predictions about the
mean evolution of both the AM amplitude and orientation up to approximately
the time when the proto-haloes collapse. After this point, proto-haloes are
increasingly affected by non-linear processes that are not taken into account
by the model. However, it has been seen in numerical simulations that, even at
very early stages, the AM of proto-haloes is systematically reoriented towards
perpendicularity with respect to the forming cosmic filaments, in
contradiction with the fixed direction expected from the TTT. In this work we
present a novel analytical approach that introduces an anisotropic scaling
factor to the standard TTT equations, which allows the AM orientation to
change in time, even during the linear regime. The amplitude and direction of
this shift depend on the large scale tidal field around the forming proto-
haloes. Our results significantly improve the predictions for the AM direction
up to the time of protohalo collapse and, in some cases, even further in time.

Large-scale structure of the universe (902) — Galaxy dark matter halos (1880)
— Intergalactic filaments (811) — Galaxy formation (595)

##  1 Introduction

The present work focuses on the angular momentum evolution of dark matter (DM)
halos within the context of the large-scale structure of the Universe.
According to the standard cosmological model, galaxies and groups of galaxies
form in the potential wells of these structures. DM halos arise from small
fluctuations in the density field of the primitive Universe. As they are
amplified by gravitational instability and virialize, they also migrate and
cluster to form a complex network of filaments, nodes, walls and voids that in
the literature is usually known as the cosmic web (Bond et al., 1996; van de
Weygaert & Bond, 2008; Aragón-Calvo et al., 2010; Cautun et al., 2014, see
Libeskind et al. 2018 for a recent revision of this topic). Hence, the study
of the spatial distribution, evolution and properties of halos within the
large-scale structure of the Universe allows us to connect phenomena on a wide
range of scales: from the determination of cosmological parameters to galactic
astrophysics.

One of the key ingredients in the models of galaxy formation is their spin,
which is usually assumed to be inherited from the angular momentum (AM) of
their hosting DM halos. In the current paradigm, the AM arises during the
early stages of structure formation, due to the coupling between the shape of
the forming proto-halo and the tidal field produced by its surrounding matter
distribution (Hoyle, 1951; Peebles, 1969; Doroshkevich, 1970; White, 1984).
This approach has been the basis of an heterogeneous family of models and
predictions that can be summarized as the tidal torque theory (TTT). The TTT
predicts the growth of AM in the frame of an isotropically expanding
Friedmann-Lemaître-Robertson-Walker universe (FLRW, Friedmann, 1924; Lemaître,
1931; Robertson, 1935; Walker, 1937, see Ellis & van Elst 1999 for a complete
review). It adopts a Lagrangian approach, considering the mass elements that
conform each proto-halo as individual particles. It also assumes that, before
shell crossing occurs, the evolution of the particles can be reasonably well
described by the Zel’dovich approximation (Zel’dovich, 1970).

In this context, if we consider a proto-halo whose moment of inertia with
respect to its center of mass is $\mathbf{I}$, located within a tidal field
$\mathbf{T}$, the $i$-th component of its AM can be expressed as a function of
the cosmic time $t$ through (White, 1984):

$J_{i}(t)=a^{2}(t)\dot{D}(t)\epsilon_{ijk}T_{jl}I_{lk},$ (1)

where $a(t)$ is the usual scale factor of the FLRW universe, $D(t)$ is the
linear growth factor that describes how density perturbations evolve in time,
the dot denotes a derivative with respect to cosmic time and $\epsilon_{ijk}$
represents the fully antisymmetric rank-three tensor (for a more detailed
description of the TTT, see e.g. Section 2 in López et al. 2019 and references
therein).

Eq. (1) states that, during the early stages of structure formation, the AM is
a result of the misalignment between the shape of proto-halos and their
surrounding tidal field. This expression provides a framework for calculating
statistical properties associated to the AM growth (e.g. Hoffman, 1986;
Heavens & Peacock, 1988; Steinmetz & Bartelmann, 1995; Sugerman et al., 2000;
Lee & Pen, 2000; Porciani et al., 2002a, b) and to compare these predictions
with results from numerical simulations.

One important thing to notice in Eq. (1) is that the time dependence of
$J_{i}(t)$ is determined solely by the isotropic factor $a^{2}(t)\dot{D}(t)$,
which implies that each component of the AM grows at the same rate. Hence,
according to this formulation, only the amplitude of the AM is expected to
change, whereas its direction should remain constant over time, at least
during the period in which the model assumptions are valid. This is a key
implication of the standard TTT that is often overlooked: the model allows to
predict preferred directions for the AM, but it can not address any variation
in the spin orientation. In fact, different implementations of this framework
that accurately estimate the AM direction with respect to the large-scale
structure (e.g. Lee & Pen, 2000; Porciani et al., 2002b), and even explain
secondary trends such as the mass dependency of the spin-filament alignment
(Codis et al., 2015), usually ignore the time factor and only focus on the
form of the tensors $\mathbf{I}$ and $\mathbf{T}$ or the correlation between
them.

##  2 Evolution of the spin-filament alignment

Figure 1: Median alignment between the AM of halos at different redshifts and
the three preferred directions associated to their embedding filaments at
present time. The indexes $i=1,2$ represent, respectively, the first and
second axes of collapse, whereas $i=3$ indicates the direction of expansion,
i.e. the spine of the filament. Each curve corresponds to a different
redshift, as indicated by the label. The median alignment is ploted as a
function of halo mass. Figure taken from López et al. 2021.

In the first part of this thesis we use DM only cosmologial simulations to
show that, despite the prevailing assumption, the spin direction of proto-
halos undergoes significant evolution even during the early stages,
systematically shifting towards perpendicularity with respect to the
developing cosmic filaments. This contradicts the fixed direction expected
from Eq. 1 and is the main result of the first part of the thesis.

In order to perform this analysis we determine, on the one hand, the evolution
of the AM of the proto-halos between $z=80$ and $z=0$ and, on the other, the
main directions of the cosmic filaments in which each halo inhabits at present
time. In the first case, after identifying virialized groups at $z=0$ using a
Friends of Friends (FOF) algorithm, we follow the particles of each group back
in time determining, at each instant $t$, the spin direcion
$\hat{\mathbf{J}}(t)$ of the corresponding Lagrangian patch. In the second
case we use the nexus+method (Cautun et al., 2013) to identify cosmic
filaments at $z=0$ and determine their principal axes $\hat{\mathbf{e}}_{i}$,
where $i=1,2$ represent the first and second direction of collapse,
respectively, and $i=3$ corresponds to the direction of expansion or spine of
the filament. Next, we characterize the evolution of the alignment between
$\hat{\mathbf{J}}(t)$ and $\hat{\mathbf{e}}_{i}$ by computing the median value
of the cosine of the angle between them.

In Figure 1 we show one of the main results of this procedure. As it can be
seen, at $z=80$ the AM has a mass-dependent preferred orientation: whereas for
all masses there is a strong trend for $\hat{\mathbf{J}}$ to be perpendicular
to $\hat{\mathbf{e}}_{1}$, low mass halos are more tipically aligned with
$\hat{\mathbf{e}}_{3}$, while high mass halos are mostly aligned with
$\hat{\mathbf{e}}_{2}$. This is cualitatively consistent with predictions from
TTT (Lee & Pen, 2000; Porciani et al., 2002b).

For $z=0$, the trends we observe are different from the early stages, but
widely known: the higher the mass of halos, the stronger their AM is
perpendicularly aligned with respect to the spine of their embedding
filaments. While this is not predicted by TTT, the usual interpretation is
that certain late non-linear processes, such as mergers, anisotropic secondary
accretion, and fly-by’s, which strongly correlate with the preferred
directions of the large-scale structure, affect the AM evolution that was
produced by tidal torques during the early stages and are ultimately
responsible for the present day alignments. However, it is clear that, at
least with respect to $\hat{\mathbf{e}}_{1}$ and $\hat{\mathbf{e}}_{3}$, there
is a significant change in the spin direction from $z=80$ to $z\sim 1$, i.e.
an important fraction of the total shift in orientation is produced when the
the assumptions of TTT are valid. Moreover, this shift is systematic and
almost mass-independent: the AM becomes progressively perpendicular to
$\hat{\mathbf{e}}_{3}$ and tend to align with $\hat{\mathbf{e}}_{1}$.

This results suggest that the TTT might be extended or modified in order to
account for the early change in spin orientation, and that the direction of
the large-scale structure must play a key role in understanding how and why
this variation occurs.

##  3 Modified TTT

Figure 2: Evolution of the alignment of the AM with respect to the three
preferred directions, $\hat{\mathbf{e}}_{i}$, with $i=1,2,3$, associated to
their embedding filaments at $z=0$. The solid lines show the median value of
the AM for DM halos in our simulation, with the errorbars representing the
$3\sigma$ bootstrap error. The dashed lines correspond to the median value
predicted by the model expressed by Eq. 2. The coloured shaded areas represent
the $3\sigma$ dispersion of the predictions of the model for $10$ realizations
with halos and large-scale tidal fields randomly shuffled.

Motivated by the above results, the next part of the thesis focuses in a
reformulation of the TTT that allows early time variation of the spin
direction. First, notice that a finite-volume region, such as the one in which
a given proto-halo and its surrounding tidal field evolve, can suffer from the
effects of perturbations on even larger scales (Akitsu et al., 2017). These
fluctuations, despite having small amplitudes, are capable of affecting the
evolution of structures at smaller scales due to the non-linear coupling of
modes corresponding to different wavelengths.

As noted by Schmidt et al. (2018), there are two leading effects that come to
play in this kind of process. On the firsts place, when the large-scale
perturbation is associated with the presence of a coherent over- or
underdensity, which results in a higher or lower local expansion rate relative
to the global expansion. Secondly, when a significant tidal force can be
associated with the long-wavelength fluctuation, which produces an increase in
the anisotropy of the local statistics. The last scenario has been analyzed in
detail by Schmidt et al. (2018), who showed that the evolution of a small
region embedded in a large-scale tidal field can be described in terms of a
modified set of cosmological parameters, in a similar way as in the “separate
universe” picture (Salopek & Bond, 1990; Wands et al., 2000).

More concretely, due to the presence of a large-scale tidal field, the region
of interest will evolve differently from the larger, isotropically expanding
background. Whereas the universe grows according to the standard scale factor
$a(t)$, our region will expand anisotropically. Moreover, within a coordinate
system rotated into the principal axes of the large-scale tidal field, this
evolution can be described simply by three scale factors, $a_{i}$, with
$i=1,2,3$.

At this point is useful to consider the expansion factor ratios
$\alpha_{i}=a_{i}/a$. These can be defined such that $\alpha_{i}\rightarrow 1$
at the limit of early times ($a\rightarrow 0$). As shown by Stücker et al.
(2018) and Schmidt et al. (2018), under certain reasonable assumptions, the
evolution of $\alpha_{i}$ can be approximated during the linear and quasi-
linear regime by:

$\alpha_{i}(t)=1-D(t)\lambda_{i},$

where $\lambda_{i}$ are the eigenvalues of the large-scale tidal field.

Hence, in a frame aligned with the surrounding large-scale tidal field, the
evolution of the AM of a proto-halo can be expressed as:

$J_{i}(t)\propto a^{2}(t)\dot{D}(t)\alpha_{j}(t)\alpha_{k}(t)\epsilon_{ijk},$
(2)

where is the value of the $i$-th component of the AM at a very early epoch,
e.g. at the initial conditions of the simulation. This equation is the most
important result in the thesis.

As an example, let us consider a proto-halo that evolves in a region that will
end up forming a cosmic filament. In this case, the large-scale tidal field is
typically characterized by two directions of collapse and a third direction of
expansion. The AM growth in the latter direction corresponds to $i=3$ and,
according to Eq. (2), it is given by:

$J_{3}(t)\propto a^{2}(t)\dot{D}(t)\alpha_{1}(t)\alpha_{2}(t).$

Since $i=1,2$ represent the two directions of collapse, we expect
$\alpha_{1,2}<1$ and, therefore, that $J_{3}(t)$ will evolve at a lower rate
than it is expected from the standard implementation of the TTT. In
opposition, the corresponding expressions for $J_{1}(t)$ and $J_{2}(t)$ depend
on $\alpha_{3}>1$, so it is likely that they will grow at a higher rate. Thus,
a rough first look at this model tells us that the AM direction of a proto-
halo that grows within a filament-to-be region will shift towards
perpendicularity with respect to the spine of the filament.

Finally, in order to test this model, we implement Eq. (2) on a simulated
population of DM halos and compare the result with the true evolution of their
AM. For this, we first calculate the large-scale tidal tensor around each
proto-halo at $z=80$ and determine the corresponding eigenvalues and
eigenvectors. Since we do not know, a priori, which long-wavelength mode
effectively couples with the region of interest, before computing the large-
scale tidal tensor we smooth the density field around each protohalo using
gaussian kernels of different radii. Hence, we choose the smoothing scale for
which the predictions minimize a given error function with respect to the true
value of the AM. To check that this method does not bias our results, we
repeat the procedure $10$ times by randomly shuffling the proto-halos and
their tidal fields, thus producing a sample of predictions where the goodness
of fit can only be spurious.

In Figure 2 we present the results of this procedure. The left (right) hand
panel shows the median evolution of the alignment between $\hat{\mathbf{J}}$
and $\hat{\mathbf{e}}_{i}$ for low (high) mass halos. Solid lines represent
the true AM measured in the simulation and the error bars indicate the
$3\sigma$ bootstrap error, while the dashed lines represent the evolution
predicted by Eq. (2). The coloured dashed regions indicate the $3\sigma$
dispersion of the values obtained with the randomly shuffled samples.

Now, both at low and high masses, there seems to be a good agreement between
the measured evolution and the prediction of our model during the linear and
quasi-linear regime, specially with respect to $\hat{\mathbf{e}}_{1}$ and
$\hat{\mathbf{e}}_{3}$. Recalling that the standard implementation of the TTT
produces a constant direction, that is, horizontal lines, Eq. (2) yields
better results up to about $z\sim 2$, although in some cases the agreement
seems to extend even further in time. Notice that the shuffled samples are not
able to reproduce this, hence probing that the method is not biasing our
results and suggesting that, indeed, the accuracy of the prediction is due to
the physical connection between the AM and the large-scale tidal field encoded
in Eq. (2).

##  4 Summary

As a general summary, in this thesis we first use N-body cosmological
numerical simulation to show that there is a systematic variation of the AM
direction of DM halos, even during the early stages of structure formation
(Fig. 1) and that this variation can not be understood in terms of the
standard implementation of the TTT (Eq. 1). Next, we present a novel
analytical approach that adopts the “separate universe” method in order to
introduce an anisotropic scaling factor to the standard TTT equations (Eq. 2).
This allows the AM orientation to change in time, even during the linear
regime. The amplitude and direction of this shift depend on the large-scale
tidal field around the forming proto-halos. Finally, we test our model using
numerical simulations. Our results significantly improve the predictions for
the AM direction up $z\sim 2$ and, in some cases, even further in time.

## References

  * Akitsu et al. (2017) Akitsu, K., Takada, M., & Li, Y. 2017, Phys. Rev. D, 95, 083522, doi: 10.1103/PhysRevD.95.083522
  * Aragón-Calvo et al. (2010) Aragón-Calvo, M. A., van de Weygaert, R., & Jones, B. J. T. 2010, Monthly Notices of the Royal Astronomical Society, 408, 2163, doi: 10.1111/j.1365-2966.2010.17263.x
  * Bond et al. (1996) Bond, J. R., Kofman, L., & Pogosyan, D. 1996, Nature, 380, 603, doi: 10.1038/380603a0
  * Cautun et al. (2013) Cautun, M., van de Weygaert, R., & Jones, B. J. T. 2013, MNRAS, 429, 1286, doi: 10.1093/mnras/sts416
  * Cautun et al. (2014) Cautun, M., van de Weygaert, R., Jones, B. J. T., & Frenk, C. S. 2014, MNRAS, 441, 2923, doi: 10.1093/mnras/stu768
  * Codis et al. (2015) Codis, S., Pichon, C., & Pogosyan, D. 2015, MNRAS, 452, 3369, doi: 10.1093/mnras/stv1570
  * Doroshkevich (1970) Doroshkevich, A. G. 1970, Astrofizika, 6, 581
  * Ellis & van Elst (1999) Ellis, G. F. R., & van Elst, H. 1999, in NATO Advanced Study Institute (ASI) Series C, Vol. 541, Theoretical and Observational Cosmology, ed. M. Lachièze-Rey, 1–116, doi: 10.48550/arXiv.gr-qc/9812046
  * Friedmann (1924) Friedmann, A. 1924, Zeitschrift fur Physik, 21, 326, doi: 10.1007/BF01328280
  * Heavens & Peacock (1988) Heavens, A., & Peacock, J. 1988, MNRAS, 232, 339, doi: 10.1093/mnras/232.2.339
  * Hoffman (1986) Hoffman, Y. 1986, ApJ, 301, 65, doi: 10.1086/163872
  * Hoyle (1951) Hoyle, F. 1951, in Problems of Cosmical Aerodynamics, 195
  * Lee & Pen (2000) Lee, J., & Pen, U.-L. 2000, ApJ, 532, L5, doi: 10.1086/312556
  * Lemaître (1931) Lemaître, G. 1931, MNRAS, 91, 483, doi: 10.1093/mnras/91.5.483
  * Libeskind et al. (2018) Libeskind, N. I., van de Weygaert, R., Cautun, M., et al. 2018, MNRAS, 473, 1195, doi: 10.1093/mnras/stx1976
  * López et al. (2021) López, P., Cautun, M., Paz, D., Merchán, M., & van de Weygaert, R. 2021, MNRAS, 502, 5528, doi: 10.1093/mnras/stab451
  * López et al. (2019) López, P., Merchán, M. E., & Paz, D. J. 2019, MNRAS, 485, 5244, doi: 10.1093/mnras/stz762
  * Peebles (1969) Peebles, P. J. E. 1969, ApJ, 155, 393, doi: 10.1086/149876
  * Porciani et al. (2002a) Porciani, C., Dekel, A., & Hoffman, Y. 2002a, MNRAS, 332, 325, doi: 10.1046/j.1365-8711.2002.05305.x
  * Porciani et al. (2002b) —. 2002b, MNRAS, 332, 339, doi: 10.1046/j.1365-8711.2002.05306.x
  * Robertson (1935) Robertson, H. P. 1935, ApJ, 82, 284, doi: 10.1086/143681
  * Salopek & Bond (1990) Salopek, D. S., & Bond, J. R. 1990, Phys. Rev. D, 42, 3936, doi: 10.1103/PhysRevD.42.3936
  * Schmidt et al. (2018) Schmidt, A. S., White, S. D. M., Schmidt, F., & Stücker, J. 2018, MNRAS, 479, 162, doi: 10.1093/mnras/sty1430
  * Steinmetz & Bartelmann (1995) Steinmetz, M., & Bartelmann, M. 1995, MNRAS, 272, 570, doi: 10.1093/mnras/272.3.570
  * Stücker et al. (2018) Stücker, J., Busch, P., & White, S. D. M. 2018, MNRAS, 477, 3230, doi: 10.1093/mnras/sty815
  * Sugerman et al. (2000) Sugerman, B., Summers, F. J., & Kamionkowski, M. 2000, MNRAS, 311, 762, doi: 10.1046/j.1365-8711.2000.03107.x
  * van de Weygaert & Bond (2008) van de Weygaert, R., & Bond, J. R. 2008, Observations and Morphology of the Cosmic Web, Vol. 740 (coso), 24, doi: 10.1007/978-1-4020-6941-3_11
  * Walker (1937) Walker, A. G. 1937, Proceedings of the London Mathematical Society, s2-42, 90, doi: https://doi.org/10.1112/plms/s2-42.1.90
  * Wands et al. (2000) Wands, D., Malik, K. A., Lyth, D. H., & Liddle, A. R. 2000, Phys. Rev. D, 62, 043527, doi: 10.1103/PhysRevD.62.043527
  * White (1984) White, S. D. M. 1984, ApJ, 286, 38, doi: 10.1086/162573
  * Zel’dovich (1970) Zel’dovich, Y. B. 1970, A&A, 5, 84


∎

11institutetext:  Lee-Ad Gottlieb 22institutetext: Ariel University
22email<EMAIL_ADDRESS>33institutetext: Eran Kaufman 44institutetext:
Ariel University
44email<EMAIL_ADDRESS>55institutetext: Aryeh Kontorovich
66institutetext: Ben-Gurion University
66email<EMAIL_ADDRESS>77institutetext: Gabriel Nivasch 88institutetext:
Ariel University
88email<EMAIL_ADDRESS>99institutetext: Ofir Pele 1010institutetext:
SanDisk
1010email<EMAIL_ADDRESS>
# Nested Barycentric Coordinate System as an Explicit Feature Map

Lee-Ad Gottlieb  Eran Kaufman  Aryeh Kontorovich  Gabriel Nivasch  Ofir Pele

(Received: date / Accepted: date)

###### Abstract

We propose a new embedding method which is particularly well-suited for
settings where the sample size greatly exceeds the ambient dimension. Our
technique consists of partitioning the space into simplices and then embedding
the data points into features corresponding to the simplices’ barycentric
coordinates. We then train a linear classifier in the rich feature space
obtained from the simplices. The decision boundary may be highly non-linear,
though it is linear within each simplex (and hence piecewise-linear overall).
Further, our method can approximate any convex body. We give generalization
bounds based on empirical margin and a novel hybrid sample compression
technique. An extensive empirical evaluation shows that our method
consistently outperforms a range of popular kernel embedding methods.

##  1 Introduction

Kernel methods provide two principal benefits: (1) They implicitly induce a
non-linear feature map, which allows for a richer space of classifiers and (2)
when the kernel trick is available, they effectively replace the dimension $d$
of the feature space with the sample size $n$ as the computational complexity
parameter. As such, these are well-suited for the ‘high dimension, moderate
data size’ regime. For very large datasets, however, naive use of kernel
methods becomes prohibitive. The cost is incurred both at the training stage,
where an optimal classifier is searched for over an $n$-dimensional space, and
at the hypothesis evaluation stage, where a sum of $n$ kernel evaluations must
be computed.

For these reasons, for large data sets, explicit feature maps are sometimes
preferred. Various approximations have been proposed to mitigate the
computational challenges associated with explicit feature maps, including
Chang et al. (2010); Maji et al. (2012); Perronnin et al. (2010); Rahimi and
Recht (2007); Vedaldi and Zisserman (2012); Li et al. (2010); ST-18; Chum-15;
ZK-13.

#### Our contribution.

We propose a new embedding method which is well-suited for the large sample
regime. Our technique consists of partitioning the space into a nested
hierarchy of simplices, and then embedding each data point into features
corresponding to the barycentric coordinates of the simplex that contains it.
We then train a linear classifier in the rich feature space obtained from the
simplices. For sample size $n$ in $d$-dimensional space, our algorithm has
runtime $O(d^{2}n)$ regardless of the dimension of the embedding space (when
the approximation parameter is taken to be fixed, see Sections 4 and 5). In
contrast, standard kernelized SVM has a runtime $O(dn^{2})$.

Additionally, our embedding technique allows for highly non-linear decision
boundaries, although these are linear within each simplex (and hence
piecewise-linear overall), as explained in Section 2. At the same time, our
approach is sufficiently robust to closely approximate realizable convex
bodies – in fact, multiple such bodies – in only linear time in fixed
dimension (Section 3). We also give generalization bounds based on empirical
margin (Theorem 4.1) and a novel hybrid sample compression technique (Theorem
4.2). Finally, we perform an extensive empirical evaluation, in which our
method consistently outperforms other explicit feature map classification
methods, including a range of popular kernel embedding methods (Section 5).

###  1.1 Related Work

Kernel approximations for explicit feature maps come in two basic varieties:
data-independent approximations to fixed kernels, and data-dependent feature
maps.

#### Data-dependent kernel approximations.

This category includes Nystrom’s approximation (Williams and Seeger, 2000),
which projects the data onto a suitably selected subspace. If $K(x,z_{i})$ is
the projection of example $\vec{x}$ onto the basis element $\vec{z}_{i}$, the
points $\\{\vec{z}_{1},\ldots,\vec{z}_{n}\\}$ are chosen to maximally capture
the data variability. Some methods select $\vec{z}_{i}$ from the sample. The
selection can be random (Williams and Seeger, 2001), greedy (Smola and
Schökopf, 2000), or involve an incomplete Cholesky decomposition (Fine and
Scheinberg, 2001). Perronnin et al. (2010) applied Nystrom’s approximation to
each dimension of the data independently, greatly increasing the efficiency of
the method.

#### Data-independent kernel approximations.

This category includes sampling the Fourier domain to compute explicit maps
for translation invariant kernels. Rahimi and Recht (2007, 2009) do this for
the radial basis function kernel, also known as Random Kitchen Sinks. Li et
al. (2010); Vedaldi and Zisserman (2012) applied this technique to certain
group-invariant kernels, and proposed an adaptive approximation to the
$\chi^{2}$ kernel. Porikli and Ozkan (2011) map the input data onto a low-
dimensional spectral (Fourier) feature space via a cosine transform. Vempati
et al. (2010) proposed a skewed chi squared kernel, which allows for a simple
Monte Carlo approximation of the feature map. Maji et al. (2012) approximated
the intersection kernel and the $\chi^{2}$ kernel by a sparse closed-form
feature map. Pele et al. (2013) suggested using not only piecewise linear
function in each feature separately but also to add all pairs of features.
Chang et al. (2010) conducted an extensive study on the usage of the second-
order polynomial explicit feature map. Bernal et al. (2012) approximated
second order features relationships via a Conditional Random Field model.

#### Decompositions and other SVM approaches.

Simplex decompositions have been used to produce proximity-based classifiers
(Belkin et al., 2018; Davies, 1996), but to the best of our knowledge, ours is
the first work to utilize either nested simplex decompositions or barycentric
centers in conjunction with SVM. Simplex decompositions are related to the
quadtree, and the quadtree has been used together with SVM for various
learning tasks (Saavedra et al., 2004; Beltrami and da Silva, 2015), but not
for the creation of a kernel embeddings. Simplex decompositions are more
efficient than quadtrees, since a simplex naturally decomposes into only $d+1$
sub-simplices (Section 2), while a quadtree cell naturally decomposes into
$2^{d}$ sub-cells.

As mentioned, our emphasis in this paper is specifically on explicit feature
maps, but there are numerous approaches to reducing kernel SVM runtime (for
example the CoreSVM of Tsang et al. (2005, 2007)). Another related paradigm is
that of Local SVM (Hao Zhang et al., 2006; Gu and Han, 2013), which assumes
continuity of the labels with respect to spacial proximity; similarly labeled
points tend to cluster together. This differs from the underlying assumption
motivating kernel SVM, which assumes that the data is approximately linearly
separable, but not necessarily clusterable. These approaches find success in
distinct settings, and are incomparable.

#### Approximating convex polytopes.

Learning arbitrary convex bodies requires very large sample size (Goyal and
Rademacher, 2009), and so we focus instead on convex polytopes defined by a
small number of halfspaces. However, the problem of finding consistent
polytopes is known to be $\mathrm{NP}$-complete even when the polytope is
simply the intersection of two hyperplanes (Megiddo, 1988). In fact, Khot and
Saket (2011) showed that “unless $\mathrm{NP}=\mathrm{RP}$, it is hard to
(even) weakly PAC-learn intersection of two halfspaces”, even when allowed the
richer class of $O(1)$ intersecting halfspaces. Klivans and Sherstov (2009)
showed that learning an intersection of $n^{\varepsilon}$ halfspaces is
intractable regardless of hypothesis representation (under certain
cryptographic assumptions). These negative results have motivated researchers
to consider the problem of discovering consistent polytopes which have some
separating margin. Several approximation and learning algorithms have been
suggested for this problem, featuring bounds with steep dependence on the
inverse margin and number of halfspaces forming the polytope (Arriaga and
Vempala, 2006; Klivans and Servedio, 2008; Gottlieb et al., 2018; Goel and
Klivans, 2018).

In contrast, we show in Section 3 that our method is capable of approximating
any convex polytope in linear time (in fixed dimension), independent of the
halfspace number and with only logarithmic dependence on the inverse margin.
It accomplishes this by finding a linear separator in the higher-dimensional
embedded space, and projecting the solution back into the origin space.
However, our approach is not strictly comparable to those above, as they are
concerned with minimizing the disagreement between the computed polytope (or
object) and the true underlying polytope with respect to the point space,
while we minimize the volume of the space between them.

##  2 The barycentric coordinate system

Here we describe the nested barycentric coordinate system embedding. We
explain its construction and description, how to embed a point from the origin
space into the new coordinate system, and how a point in the embedded system
can be projected back into the origin space (Section 2.1). We then show that
if we associate a weight with each simplex point, then the embedding and
weights together imply some (not necessarily convex) polytope on the origin
space (Section 2.2). Later in Section 3, we will show that this system is
sufficiently robust that it can be used to approximate any convex body.

###  2.1 Nested barycentric embedding

Let $S\subset\mathbb{R}^{d}$ be a regular simplex of unit side-length, and let
$\\{q_{0},\ldots,q_{d}\\}$ be its vertices. Each point $\vec{x}$ inside the
simplex can be written using the barycentric coefficients:

$\displaystyle\vv x=\sum_{i=0}^{d}\alpha_{i}(\vv x)\vv q_{i}$ (1)
$\displaystyle\sum_{i=0}^{d}\alpha_{i}(\vv x)=1\quad 0\leq\alpha_{i}\leq 1$

Here $\alpha_{i}(\vv x)$ denotes the coefficient of point $\vv x$
corresponding to vertex $q_{i}$. Let the ordered vector of $\alpha$’s,
$\\{\alpha_{0},\ldots,\alpha_{d}\\}$, corresponding to $\vv x$ be denoted as
$\phi_{d+1}(\vv x)$. If we artificially augment the original feature space by
adding another feature which equals to 1, i.e.
$\vec{x}=(x_{0},\ldots,x_{d-1},1)$ and
$\vec{q}_{t}=(q_{1t},\ldots,q_{d-1,t},1)$ and define the matrix
$Q_{t}:=(\vec{q}_{0},\dots,\vec{q}_{t})$, then the transformation
$\phi_{d+1}(\vv x):\mathbb{R}^{d+1}\rightarrow\mathbb{R}^{d+1}$ is a linear
transformation of the form $\vec{x}=Q\vec{\alpha}$.

We can further refine the system by introducing a new point $q_{d}$ inside the
simplex, thereby splitting the simplex into $d+1$ new sub-simplices. We order
the coordinates of our system as $\\{q_{0},\ldots,q_{d}\\}$. A point $\vv x$
inside the system is embedded by first utilizing the $d+1$ vertices of its
surrounding simplex to compute the barycentric coefficients (the $\alpha$’s)
of equation 1. Then $\vv x$ is assigned a vector wherein a coordinate
corresponding to one of these $d+1$ simplex vertices is set to the coefficient
of that vertex, and all other coordinates are set equal to 0. This defines the
embedding $\phi_{d+2}(\vv x):\mathbb{R}^{d+1}\rightarrow\mathbb{R}^{d+2}$.

The refinement process can be continued by choosing points inside simplices to
further split these simplices. We define the nested architecture $B_{t}$ and
its associated embedding $\phi_{t}(\vec{x})$ to be the coordinates
$\\{\vec{q}_{0},\ldots,\vec{q}_{t}\\}$ constructed from $B_{t-1}$ by
concatenating a new point $\vec{q}_{t}$ at step $t$ to the previous coordinate
system. Each point $\vv x$ is embedded using the barycentric coefficients of
the vertices of the simplex surrounding point $\vec{x}$ and by assigning those
coefficients in the index of the corresponding vertices and by assigning zero
to all other vertices. We note that the embedding — the nested barycentric
coordinate system — is sparse, as only $d+1$ coefficients are non-zero, and
also that the embedded points lie on the $L_{1}$ sphere ($\sum\alpha=1$).

(a) step 1

(b) step 2.1

(c) step 2.2

(d) step 3

(e) step 4

Figure 1: Creation of the nested system about a convex polytope

A point in the embedded space can be projected back into the origin space by
utilizing the identity

$\displaystyle\vv x=\sum_{i=0}^{t}\alpha_{i}(\vv x)\vv q_{i}$ (2)

###  2.2 Weights, hyperplanes and polytopes

Given an embedding, we will assign a set of weights $\vv w$ to the vertices
$\\{\vec{q}_{0},\ldots,\vec{q}_{t}\\}$. Then the set of points $R$ such that:

$R=\\{\vec{x}\in S:\vec{w}\cdot\phi_{t}(\vec{x})\geq 0\\}$ (3)

is a union of regions whose boundaries are unions and intersections of
hyperplanes. $R$ can represent a polytope as well as the union of several
disjoint polytopes, each of which is not necessarily convex (see Figure 2 for
an illustration):

###### Lemma 1

Any hyperplane that crosses a single simplex can be defined by a set of
weights $\vv w=\\{w_{0},\ldots,w_{d}\\}$, such that all points $\vv x$ that
lie on the hyperplane satisfy the equation $\vv w\cdot\phi_{d+1}(\vv x)=0$.
Further, $R$ is a union of regions whose boundaries are unions and
intersections of hyperplanes, where each simplex contains at most one
hyperplane.

###### Proof

Choose $d$ linearly independent points on the given hyperplane. Since these
points are inside the coordinate system, they have unique barycentric
coefficients and thus a unique representation. Finding these weights is
equivalent to solving $A\cdot\vv{w}=\vv{0}$, where $A$ which is a matrix of
dimension $d\times(d+1)$ whose rows are the embeddings $\phi_{d+1}(\vv x)$ of
the points. This is a homogeneous linear system and so the $w$’s are unique up
to a scaling factor. Every point on the hyperplane is a linear combination of
those $d$ linearly independent points and thus also satisfies the equation
$\sum_{i}w_{i}\alpha_{i}=0$. Likewise, every set of weights represents at most
one hyperplane crossing the system.

Figure 2: An example of an open polytope and two disjoint polytopes as a
nested barycentric system

In Section 3, we will show that a simple nested barycentric system, together
with a prudent choice of weights, can be used to closely approximate any given
convex body. To this end, we will require a useful property of these systems —
essentially, that splitting a simplex cannot decrease the expressiveness of
the system. Recall that a barycentric system $B_{k}$ is defined by an ordered
set of points; we will say that $B_{k}$ is contained in $B_{t}$ ($B_{k}\subset
B_{t}$) if $B_{k}$ is a prefix of $B_{t}$.

###### Theorem 2.1

Let $B_{k}$ be a nested barycentric system, with $\\{q_{0},\ldots,q_{k}\\}$ as
its coordinates, and let $B_{t}$ be a nested barycentric system such that
$B_{k}\subset B_{t}$. Let $P$ be a polytope described in $B_{k}$ as:

$P=\\{\vec{x}\in S:\vec{w}\cdot\phi_{k}(\vec{x})\geq 0\\}$ (4)

then there exist a set of weights $\vec{w}^{\prime}$ such that $P$ can also be
described by $B_{t}$. Further, $\vec{w}$ is a prefix of $\vec{w}^{\prime}$.

In order to prove the theorem we must first demonstrate the relationship
between coefficients before and after a simplex split.

###### Definition 1

Let $B_{t}$ be a nested barycentric system, with $\\{q_{0},\ldots,q_{t}\\}$,
Let the new splitting point be $q_{t+1}$. Since $q_{t+1}\in B_{t}$, it can be
written as:

$q_{t+1}=\sum_{i=1}^{t}\beta_{i}\;\vv{q}_{i}$ (5)

We define $\beta_{i}$ to be the coefficients of the new coordinate of step
$t+1$ using the coordinate system at step $t$.

###### Lemma 2

For a given data point $\vv p$ the connection between the coefficients of step
$t$ and $t+1$ is:

$\alpha_{i,t}(\vv p)=\alpha_{i,t+1}(\vv p)+\beta_{i}\alpha_{t+1,t+1}(\vv p)$
(6)

For the simplicity of the notation in this proof we will use $\alpha_{i}$
instead of $\alpha_{i}(\vv p)$ , and $\alpha^{*}$ instead of
$\alpha_{t+1,t+1}(\vv p)$.

###### Proof

The data point $\vv p$ at step $t$ can be written as:

$\vv p=\sum_{i=1}^{t}{\alpha}_{i,t}\vv{q}_{i}$ (7)

The point $\vv p$ at step $t+1$ is written as:

$\vv
p=\sum_{i=1}^{t+1}{\alpha}_{i,t+1}\vv{q}_{i}=\sum_{i=0}^{t}\alpha_{i,t+1}\vv{q}_{i}+\alpha^{*}\vv{q}_{t+1}$
(8)

Combining equations 5 and 8, we derive:

$\vv p=\sum_{i=1}^{t}(\alpha_{i,t+1}+\beta_{i}\alpha^{*})\vv{q}_{i}$ (9)

Since the barycentric representation is unique, equations 7 and 9 together
imply:

$\alpha_{i,t}=\alpha_{i,t+1}+\beta_{i}\alpha^{*}$ (10)

We can now prove theorem 2.1 by induction:

###### Proof

For a given polytope $P$ with a set of weights $\vec{w}_{t}$ at system
$B_{t}$, such that $P=\\{\vec{x}\in S:\vec{w}_{t}\cdot\phi_{t}(\vec{x})\geq
0\\}$, and $B_{t}\subset B_{t+1}$, we choose the set of weights
$\vec{w}_{t+1}$ for $B_{t+1}$ as follows: The first $t$ weights of $B_{t+1}$
are the same as for $B_{t}$ ($w_{i,t}=w_{i,t+1}\quad\forall i<t+1$), and
$w_{t+1,t+1}=\sum_{i}\beta_{i}w_{i}(t)$. Then the scaled distance of every
given point represented in $B_{t}$ from the hyperplane
$\gamma_{t}=\vec{w}_{t}\phi_{t}(\vec{x})$, is the same as the scaled distance
of the point represented in
$B_{t+1}:\gamma_{t+1}=\vec{w}_{t+1}\phi_{t+1}(\vec{x})$, and specifically the
polytope $P$ remains the same. Using Lemma 2 we have:

$\displaystyle\gamma_{t+1}$
$\displaystyle=\sum_{i=0}^{t+1}\alpha_{i,t+1}w_{i,t+1}$
$\displaystyle=\sum_{i=0}^{t}\alpha_{i,t+1}w_{i,t+1}+\alpha^{*}w_{t+1,t+1}$
$\displaystyle=\sum_{i=0}^{t}(\alpha_{i,t}-\beta_{i}\alpha^{*})w_{i,t+1}+\alpha^{*}w_{t+1,t+1}$
$\displaystyle=\underbrace{\sum_{i=0}^{t}\alpha_{i,t}w_{i,t}}_{=\gamma_{t}}-\alpha^{*}{\sum_{i=0}^{t}\beta_{i}w_{i,t}}+{\alpha^{*}w_{t+1,t+1}}$
$\displaystyle=\gamma_{t}+\alpha^{*}\underbrace{(w_{t+1,t+1}-\sum_{i=0}^{t}\beta_{i}w_{i,t})}_{=0}$
$\displaystyle=\gamma_{t}.$

##  3 Approximating a convex body

In this section we show that the nested barycentric coordinate system (NBCS)
can represent an arbitrarily close approximation to any convex body. As stated
the NBCS produces a (not necessarily convex) piece-wise linear classifier. In
fact, this method can approximate multiple convex bodies. For simplicity, we
focus on the case of a single convex body, and demonstrate how our method
approximates it. This will be done by placing split points at the barycenters
of their containing simplices, where the barycenter of a simplex with vertices
$p_{0},\ldots,p_{d}$ is given by $(p_{0}+\cdots+p_{d})/(d+1)$.

In order to state our result formally, we introduce some notation: Given a
point $p\in\mathbb{R}^{d}$ and a parameter $\varepsilon>0$, let
$B_{\varepsilon}(p)=\\{q\in\mathbb{R}^{d}:\|q-p\|_{2}\leq\varepsilon\\}$ be
the ball of radius $\varepsilon$ centered at $p$. Given a set
$X\subseteq\mathbb{R}^{d}$, let $X^{(-\varepsilon)}=\\{p\in
X:B_{\varepsilon}(p)\subseteq X\\}$ be the set of all points of $X$ that are
at distance at least $\varepsilon$ from the boundary of $X$. Recall that $S$
denotes the unit simplex.

###### Theorem 3.1

Let $P\subseteq S$ be a given convex body of diameter 1, and let
$0<\varepsilon<1$ be given. Then there exists a nested system $B_{t}$,
obtained by always placing split points at the barycenters of their containing
simplices, and a corresponding set of weights $\vec{w}$, such that

$\tilde{P}=\\{\vec{x}\in S:\vec{w}\cdot\phi_{t}(\vec{x})\geq 0\\}$ (11)

satisfies the following:

  1. 1.

$\operatorname{vol}(\tilde{P}\setminus P)<\varepsilon\operatorname{vol}(S)$.

  2. 2.

$\tilde{P}^{(-\varepsilon)}\subseteq P\subseteq\tilde{P}$.

#### Proof

The construction proceeds in stages $i=0,1,\ldots,s$. (Below, we will take
$s=2^{O(d)}\ln^{2}(1/\varepsilon)$.) At stage $0$ the only points present are
the vertices of $S$. At each stage $i$, $i\geq 1$, a new split point is placed
at the barycenter of each existing simplex, and the final construction is
called the $s$-stage _uniform subdivision_ of $S$. Let $A_{i}$ be the set of
simplices present at stage $i$, and clearly $|A_{i}|=(d+1)^{i}$. Note that all
simplices in $A_{i}$ have the same volume.

The weights $w_{i}$ are assigned as follows: Initially, vertices
$q_{0},\ldots,q_{d}$ of $S$ are assigned weights $w_{0}=\cdots=w_{d}=-1$. At
each stage $i\geq 1$, each new split point is given the smallest possible
weight that ensures $\tilde{P}\supseteq P$, where $\tilde{P}$ is given by
(11). Once a weight is assigned to a point, it is never changed again. In
other words, for those points of $B_{i+1}$ that already belonged to $B_{i}$,
their weights at $B_{i+1}$ are the same as their weights at $B_{i}$.

Let $S^{\prime}\in A_{i}$ be a simplex with vertices
$q_{i_{0}},\ldots,q_{i_{d}}$ and weights $w_{i_{0}},\ldots,w_{i_{d}}$,
respectively. Let $q^{\prime}=(q_{i_{0}}+\cdots+q_{i_{d}})/(d+1)$ be the
barycenter of $S^{\prime}$. By Theorem 2.1, if $q^{\prime}$ is assigned weight
$w_{\mathrm{avg}}=(w_{i_{0}}+\cdots w_{i_{d}})/(d+1)$, then $\tilde{P}\cap
S^{\prime}$ remains unchanged. Hence, the weight $w^{\prime}$ that will be
assigned to $q^{\prime}$ by our construction will satisfy $w^{\prime}\leq
w_{\mathrm{avg}}$. And therefore, at each stage, $\tilde{P}$ only shrinks. If
at stage $i$ a certain simplex $S^{\prime}\in A_{i}$ satisfies $S^{\prime}\cap
P=\emptyset$, then at stage $i+1$ the barycenter of $S^{\prime}$ will be
assigned weight $-\infty$, so that the interior of $S^{\prime}$ will lie
completely outside of $\tilde{P}$.

Let us denote by $\tilde{P}_{s}$ the region $\tilde{P}$ produced by this
construction after stage $s$. (See Figure 3 for an illustration in the plane.)
We will now prove that, if $s$ is made large enough, then $\tilde{P}_{s}$
approximates the given convex body $P$ arbitrarily well, as stated in the
theorem.

Figure 3: Four stages of the approximation of a given convex polygon in the
plane.

The _diameter_ of a compact subset of $\mathbb{R}^{d}$ is the maximum distance
between two points in the set. In particular, the diameter of a simplex is the
largest distance between two vertices of the simplex.

###### Lemma 3

Let $S^{\prime}$ be a simplex with vertices $p_{0},\ldots,p_{d}$, let $c$ be
the diameter of $S^{\prime}$, and let $q$ be the barycenter of $S^{\prime}$.
Then the distance between $q$ and any vertex $p_{i}$ is at most $cd/(d+1)$.

###### Proof

Fix $p_{i}=\vec{0}$ for concreteness. Then, under the constraints
$\|p_{j}\|_{2}\leq c$ for $j\neq i$, the distance between $q$ and $p_{i}$ is
maximized by letting $p_{j}=(c,0,\ldots 0)$ for all $j\neq i$, which yields
the claimed distance.

###### Lemma 4

Let $S^{\prime}$ be a simplex with diameter $c$. Let $A$ be the collection of
the $(d+1)^{d}$ simplices obtained by a $d$-stage uniform subdivision of
$S^{\prime}$. Then there are at least $(d+1)!$ simplices in $A$ with diameter
at most $cd/(d+1)$.

###### Proof

By Lemma 3, every simplex in $A$ that contains at most one vertex of
$S^{\prime}$ will have diameter at most $cd/(d+1)$. Each time a simplex
$S^{\prime\prime}$ is subdivided into $d+1$ simplices by an interior point
$q$, the new simplices share only $d$ of their vertices with
$S^{\prime\prime}$. Hence, at stage $1$ of the subdivision of $S^{\prime}$,
there are $d+1$ simplices that share only $d$ vertices with $S^{\prime}$; at
stage $2$, there are $(d+1)d$ simplices that share only $d-1$ vertices with
$S^{\prime}$; and so on, until at stage $d$ there are $(d+1)d\cdots 2=(d+1)!$
simplices that share only one vertex with $S^{\prime}$.

Recall that $A_{i}$ denotes the collection of simplices present in the
$i$-stage uniform subdivision of $S$.

###### Lemma 5

Let $k,z$ be integers, and set $s=zkd$. Then at most a
$\bigl{(}z(1-e^{-d})^{k}\bigr{)}$-fraction of the simplices in $A_{s}$ have
diameter larger than $(d/(d+1))^{z}$.

###### Proof

By repeated application of Lemma 4. After $kd$ stages, at most an
$\alpha$-fraction of the simplices in $A_{kd}$ have diameter larger than
$d/(d+1)$, for $\alpha=\left(1-\frac{(d+1)!}{(d+1)^{d}}\right)^{k}$. All the
other simplices have diameter at most $d/(d+1)$. Of the latter simplices,
after $kd$ more stages, at most an $\alpha$-fraction of their descendants have
diameter larger than $(d/(d+1))^{2}$. Hence, in $A_{2kd}$, the fraction of
simplices with diameter larger than $(d/(d+1))^{2}$ is at most
$\alpha+(1-\alpha)\alpha<2\alpha$. And so on. In $A_{zkd}$, the fraction of
simplices with diameter larger than $(d/(d+1))^{z}$ is at most $z\alpha$.
Since $(d+1)!/(d+1)^{d}>e^{-d}$ for all $d$, the claim follows.

Now, given $\varepsilon$, let $\rho=\varepsilon/(2\sqrt{2}d^{2})$. Choose $z$
minimally so that $(d/(d+1))^{z}\leq\rho$, and then choose $k$ minimally so
that $z(1-e^{-d})^{k}\leq\varepsilon/2$. Let $s=zkd$. (Hence, we have $s\leq
c^{d}\ln^{2}(1/\varepsilon)$ for some $c$.) Let $Z_{1}$ be the region
surrounding $P$ that is at distance at most $\rho$ from $P$, and let $Z_{2}$
be the union of all the simplices in $A_{s}$ with diameter larger than $\rho$.
By the choice of $s$, every point in $\tilde{P}_{s}\setminus P$ belongs to
$Z_{1}\cup Z_{2}$. Let us bound each of $\operatorname{vol}(Z_{1})$ and
$\operatorname{vol}(Z_{2})$.

As $\rho\to 0$ (keeping $P$ fixed) we have
$\operatorname{vol}(Z_{1})\leq(1+o(1))\rho\operatorname{surf}(P)$.
Furthermore, $P$ and $S$ are both convex with $P\subseteq S$, so
$\operatorname{surf}(P)\leq\operatorname{surf}(S)$. Since $S=S_{d}$ where
$S_{d}\subset\mathbb{R}^{d}$ is a regular simplex of unit side-length, we have
$\operatorname{vol}(S_{d})=\sqrt{d+1}/(d!\sqrt{2^{d}})$ and
$\operatorname{surf}(S_{d})=(d+1)\operatorname{vol}(S_{d-1})\approx\sqrt{2}d^{2}\operatorname{vol}(S_{d})$.
Hence, by the choice of $\rho$, we have
$\operatorname{vol}(Z_{1})\leq(\varepsilon/2)\operatorname{vol}(S)$. By Lemma
5, we also have
$\operatorname{vol}(Z_{2})\leq(\varepsilon/2)\operatorname{vol}(S)$. Hence,
$\operatorname{vol}(\tilde{P}_{s}\setminus
P)\leq\varepsilon\operatorname{vol}(S)$, and the first item follows.

For the second item, by construction $P\subseteq\tilde{P}$. Now given a
parameter $\delta>0$, apply the first part of the theorem with
$\varepsilon=\operatorname{vol}(B_{\delta})/(2\operatorname{vol}(S))$, where
$\operatorname{vol}(B_{\delta})\approx\delta^{d}\pi^{d/2}/(d/2)!$ is the
volume of a $d$-dimensional ball of radius $\delta$. (A calculation shows that
$\varepsilon\geq\delta^{d}$, so it suffices to take
$s=(c^{\prime})^{d}\ln^{2}(1/\delta)$ for an appropriate constant
$c^{\prime}$.) Suppose for a contradiction that there exists a point
$p\in\tilde{P}_{s}^{(-\delta)}$ that is outside of $P$. Then the ball
$B=B_{\delta}(p)$ is contained in $\tilde{P}$. But since $P$ is convex, more
than half of $B$ is outside of $P$. Hence,
$\operatorname{vol}(\tilde{P}_{s}\setminus
P)>\operatorname{vol}(B)/2=\varepsilon\operatorname{vol}(S)$, contradicting
the first part of the theorem. This implies that
$\tilde{P}_{s}^{(-\delta)}\subseteq P$, concluding the second item and the
proof of Theorem 3.1.

##  4 Learning algorithms

In Section 3, we demonstrated that the uniform subdivision embedding, coupled
with an appropriate choice of weights, can represent an approximation to any
given convex body. This motivates an embedding technique for a linear
classifier.

For some parameter $q$ (determined by cross validation), our classification
algorithm produces a $q$-stage uniform subdivision: Beginning with a single
simplex covering the entire space, at each stage we add to the system the
barycentric center of each simplex, thereby splitting all simplices into $d+1$
sub-simplices. We call a set of $d+1$ simplices formed by a split siblings.
The procedure stops after $q$ stages, having produced $(d+1)^{q}$ simplices.
We note that there is nothing to be gained by splitting an empty simplex, so
the algorithm may ignore these; then an empty simplex must have a sibling that
contains points, and since a simplex has $d$ siblings, we have that the total
number of simplices is not greater than $\min\\{(d+1)^{q},dnq\\}$. Parameter
$q$ is analogous to depth parameter $s$ of Lemma 5; however, we have
consistently observed by empirical cross-validation that it suffices to take
$q$ as a very small constant (at most 5), and so we stipulate in our algorithm
that $q$ be bound by a small universal constant.

Having computed the nested coordinate system, we use it to embed all points
into high-dimensional space. To find an appropriate weight assignment
$\vec{w}$ for the simplex points, we compute a linear classifier on the
embedded space to separate the data. A linear classifier takes the form
$h(\vec{x})={\mbox{sign}}(\vec{w}\cdot\vec{x})$, and this $\vec{w}$ serves as
our weight vector for the embedding. We use soft SVM as our linear classifier,
and note that the training phase can be executed in time $O(dn)$ on
$(d+1)$-sparse vectors (Joachims, 2006). The total runtime of the algorithm is
bounded by the cost of executing the sparse SVM plus the total number of
simplex points, that is
$O(\min\\{d(d+1)^{q}+dn,d^{2}qn\\}=\min\\{d^{O(1)}+dn,O(d^{2}n)\\}$).

To classify a new point, we can simply search top-bottom for its lowest
containing simplex: We begin at the initial simplex, investigate which of its
$d$ sub-simplices contains the query point, and iterate on that simplex. This
can all be done in time $O(qd^{2})=O(d^{2})$. After bounding the run time, we
want to bound the out of sample error:

###### Theorem 4.1

If our classifier achieves sample error $\hat{R}$ with margin $\gamma$ (i.e.,
$\hat{R}$ is the fraction of the points whose margin is less than $\gamma$) on
a sample of size $n$ after stopping at stage $q$, its generalization error $R$
is bounded by

$\hat{R}+O(1/(\gamma\sqrt{n})+\sqrt{\log(q/\delta)/n})$ (12)

with probability at least $1-\delta$.

This bound is a consequence of the SVM margin bound (Mohri et al., 2012,
Theorem 4.5) and the stratification technique (Shawe-Taylor et al., 1998),
where the $q$-th stage receives weight $1/2^{q}$.

#### Adaptive splitting strategies.

The above algorithm is data-independent in its selection of split points. It
is reasonable to suggest that a data-dependent choice of split points can
improve the performance of the learning algorithm. Several greedy strategies
suggest themselves, but after empirical trials we suggest the following split
heuristic: At every stage, a linear classifier of the embedding space is
computed. For each simplex, we identify the points in the simplex have been
misclassified so far, and choose a data point which is closest to the the
barycentric center of the misclassified points. As before, we limit the
heuristic to a constant number of stages, and it is also not necessary to
subdivide an empty simplex, or one that contains not many misclassified
points. (See Section 5 for empirical results.) The following bounds follow
from Corollary 2:

###### Theorem 4.2

If our adaptive classifier achieves sample error $\hat{R}$ with margin
$\gamma$ (i.e., $\hat{R}$ is the fraction of the points whose margin is less
than $\gamma$) on a sample of size $n$ after stopping at stage $q$ and
retaining $k$ split points, its generalization error $R$ is bounded by

$\hat{R}+O(1/(\gamma\sqrt{n-k})+\sqrt{\log(q/\delta)/(n-k)})$ (13)

with probability at least $1-\delta$.

##  5 Experiments

Our embedding technique is motivated by provable bounds for convex polytopes,
but we find that it is sufficiently robust to yield impressive empirical
results for non-convex polytopes or even general point sets. All experiments
utilized the python scikit-learn library (Pedregosa et al., 2011) 111code can
be found at https://github.com/erankfmn/NBCS-embedding. The regularization
parameter $C$ was 5-fold cross-validated over the set
$\\{2^{-5},2^{-3},\ldots,2^{15}\\}$, and for the RBF kernel, the $\gamma$
parameter was five-fold cross-validated over the set
$\\{2^{-15},2^{-3},\ldots,2^{3}\\}$. For our methods, the maximum iteration
parameter $q$ was cross validated over the set $\\{2,\ldots,5\\}$. Our
algorithms usually converged even before reaching the maximum number of
allowed iterations.

(a) step 1

(b) step 2

(c) step 3

(d) step 4

Figure 4: Learning a polytope separating the red and blue points.

#### Non-convex polytope approximation.

Before presenting the experiments, we give a simple example that illustrates
the power of our approach in approximating non-convex polytopes. We created a
random data-set wherein all positive examples were taken from within a $5$-gon
and the negative points from outside it. This data was randomly generated
within the unit circle: Each vector was sampled from the unit sphere and then
normalized by $u^{1/d}$, where random variable $u\in[0,1]$ is sampled
independently at random for each vector. We then sampled 5 halfspaces whose
intersection formed the target polytope: For each halfspace, we sampled a
random direction vector $w_{j}$ uniformly from the unit sphere, and then
sampled a random offset value $b_{j}\in[.05,.95]$ to produce the halfspace
$(w_{j},b_{j})$. The intersection of these halfspaces is the target polytope.
All data points inside the polytope with margin 0.05 were labeled as positive,
all data points outside the polytope with margin 0.05 were labeled as
negative, and the rest were discarded.

Figure 4 shows the iterative boundary formation, where the bold black line is
the decision boundary and the dotted lines are the margin
($\vec{w}\cdot\phi_{t}(x)=\pm 1$) . For each iteration, the nested barycentric
system is illustrated by the red lines. A consistent approximation of the
underlying polytope for multiple runs was achieved after only 3 iterations.
Notice how the margins become smaller at each iteration until reaching their
predetermined size.

#### Benchmarks.

We first compared the runtime and accuracy of our methods in Section 4 –
uniform subdivision with NBCS (uni-NBCS) and adaptive splitting with NBCS
(adapt-NBCS) – to the 2nd and 3rd degree polynomial explicit feature maps, and
to the RBF kernel SVM. We used CoreSVM for the RBF kernel, as the LibSVM RBF
failed to run on very large datasets. We considered large datasets from LibSVM
Machine Learning repository (Chang and Lin, 2011), taking random $70-30\%$
splits averaged over $10$ random trials. In the LibSVM implementation, the
runtime of 2nd degree SVM is $O(d^{2}n)$ and 3rd degree SVM is $O(d^{3}n)$. We
implemented our algorithm to run in $O(d^{2}n)$ time. Table 1 shows a summary
of our experimental results, and demonstrates that our method compares
favorably to the others both in runtime and accuracy. We believe that this is
due to NBCS embedding the data into a small but yet very expressive space. We
further compared our technique to other explicit feature map methods. Here we
focused on accuracy as opposed to runtime, since all these methods have
similar runtime complexity, Figure 5 demonstrates a comparison of the average
accuracy between our embedding technique (adapt-NBCS), Kitchen Sink (KS)
(Rahimi and Recht, 2007), Nystrom’s approximation (Williams and Seeger, 2000)
and the adaptive $\chi^{2}$ (Vedaldi and Zisserman, 2012), all of which have
open source implementations, over a large variety of medium sized datasets. We
also included the accuracy achieved by RBF CoreSVM. Again, our algorithm’s
accuracy compared favorably with the others.

##  6 Discussion and future work

In this paper, we introduced the barycentric coordinate system embedding,
demonstrated its computational power, and suggested implementation techniques.
We derived a statistical foundation for this approach, and presented
experiments on LibSVM datasets which show promising empirical results. This
method is advantageous in the large data and small to medium feature size
regime. Future work includes analytical and empirical investigations of other
natural splitting strategies.

Dataset | $n$ | $d$ | 2nd degree SVM | 3rd degree SVM | CoreSVM-RBF | uni-NBCS | adapt-NBCS
---|---|---|---|---|---|---|---
letter | 20,000 | 16 | 84%, 12.3 sec | 89.2%, 81.7 sec | 81%, 38 sec | 90.5%, 14 sec | 91.5%, 17 sec
SkinNonSkin | 245,057 | 4 | 99.25%, 13 sec | 99.4%, 20 sec | 98.9%, 570.4 sec | 97.6%, 4 sec | 98.8%, 4.2 sec
cod-rna | 59,535 | 8 | 94.9%, 9 sec | 95.2%, 18.6 sec | 94.3%, 23 sec | 93.6%, 8.7 sec | 94.5%, 9 sec
shuttle | 58,000 | 9 | 96%, 8 sec | 98%, 25.8 sec | 93.2%, 5.3 sec | 95.4%, 8 sec | 97.8%, 6.3 sec
covtype | 581,012 | 54 | 79%, 1950 sec | 81.5%, 8028 sec | 83.5%, 10028 sec | 82.3%, 2040 sec | 82.5%, 2140 sec
Table 1: UCI Datasets

Transf Steel Cardio3 Cardio10 Landsat Segment $80$$90$accuracy rate
(%)CoreSVM-RBFPOLYNYSTKSCHI-2 adapt-NBCS

IrisWine Ion Libras Sonar $80$$90$$100$accuracy rate (%)coreSVM-
RBFPOLYNYSTKSCHI-2adapt-NBCS

Figure 5: classification results for different embedding techniques

## References

  * Anthony and Bartlett (1999) Anthony M, Bartlett PL (1999) Neural Network Learning: Theoretical Foundations. Cambridge University Press, Cambridge, DOI 10.1017/CBO9780511624216, URL http://dx.doi.org/10.1017/CBO9780511624216
  * Arriaga and Vempala (2006) Arriaga RI, Vempala S (2006) An algorithmic theory of learning: Robust concepts and random projection. Machine Learning 63(2):161–182, URL https://doi.org/10.1007/s10994-006-6265-7
  * Belkin et al. (2018) Belkin M, Hsu DJ, Mitra P (2018) Overfitting or perfect fitting? risk bounds for classification and regression rules that interpolate. In: Bengio S, Wallach H, Larochelle H, Grauman K, Cesa-Bianchi N, Garnett R (eds) Advances in Neural Information Processing Systems 31, Curran Associates, Inc., pp 2300–2311, URL http://papers.nips.cc/paper/7498-overfitting-or-perfect-fitting-risk-bounds-for-classification-and-regression-rules-that-interpolate.pdf
  * Beltrami and da Silva (2015) Beltrami M, da Silva ACL (2015) Grid-quadtree algorithm for support vector classification parameters selection. Appl Math Sci 9:75–82
  * Bernal et al. (2012) Bernal A, Crammer K, Pereira F (2012) Automated gene-model curation using global discriminative learning. Bioinformatics
  * Chang and Lin (2011) Chang CC, Lin CJ (2011) LIBSVM: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology 2:27:1–27:27, software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm
  * Chang et al. (2010) Chang Y, Hsieh C, Chang K, Ringgaard M, Lin C (2010) Training and testing low-degree polynomial data mappings via linear SVM. JMLR
  * Davies (1996) Davies S (1996) Multidimensional triangulation and interpolation for reinforcement learning. In: Advances in Neural Information Processing Systems 9, NIPS, Denver, CO, USA, December 2-5, 1996, pp 1005–1011, URL http://papers.nips.cc/paper/1229-multidimensional-triangulation-and-interpolation-for-reinforcement-learning
  * Fine and Scheinberg (2001) Fine S, Scheinberg K (2001) Efficient SVM training using low-rank kernel representations. Journal of Machine Learning Research 2:243–264, URL http://www.jmlr.org/papers/v2/fine01a.html
  * Goel and Klivans (2018) Goel S, Klivans A (2018) Learning neural networks with two nonlinear layers in polynomial time (arxiv:1709.06010v4)
  * Gottlieb et al. (2018) Gottlieb L, Kaufman E, Kontorovich A, Nivasch G (2018) Learning convex polytopes with margin. In: NeurIPS, pp 5711–5721
  * Goyal and Rademacher (2009) Goyal N, Rademacher L (2009) Learning convex bodies is hard, arxiv:0904.1227
  * Gu and Han (2013) Gu Q, Han J (2013) Clustered support vector machines. In: Artificial Intelligence and Statistics, pp 307–315
  * Hanneke and Kontorovich (2019) Hanneke S, Kontorovich A (2019) A sharp lower bound for agnostic learning with sample compression schemes. In: ALT
  * Hao Zhang et al. (2006) Hao Zhang, Berg AC, Maire M, Malik J (2006) Svm-knn: Discriminative nearest neighbor classification for visual category recognition. In: 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’06), vol 2, pp 2126–2136
  * Joachims (2006) Joachims T (2006) Training linear SVMs in linear time. In: KDD
  * Khot and Saket (2011) Khot S, Saket R (2011) On the hardness of learning intersections of two halfspaces. J Comput Syst Sci 77(1):129–141, URL https://doi.org/10.1016/j.jcss.2010.06.010
  * Klivans and Servedio (2008) Klivans AR, Servedio RA (2008) Learning intersections of halfspaces with a margin. J Comput Syst Sci 74(1):35–48, URL https://doi.org/10.1016/j.jcss.2007.04.012
  * Klivans and Sherstov (2009) Klivans AR, Sherstov AA (2009) Cryptographic hardness for learning intersections of halfspaces. J Comput Syst Sci 75(1):2–12, URL https://doi.org/10.1016/j.jcss.2008.07.008
  * Li et al. (2010) Li F, Ionescu C, Sminchisescu C (2010) Random Fourier Approximations for Skewed Multiplicative Histogram Kernels, Springer Berlin Heidelberg, Berlin, Heidelberg, pp 262–271. URL https://doi.org/10.1007/978-3-642-15986-2_27
  * Maji et al. (2012) Maji S, Berg A, J M (2012) Efficient classification for additive kernel SVMs. PAMI
  * Megiddo (1988) Megiddo N (1988) On the complexity of polyhedral separability. Discrete & Computational Geometry 3(4):325–337, URL https://doi.org/10.1007/BF02187916
  * Mohri et al. (2012) Mohri M, Rostamizadeh A, Talwalkar A (2012) Foundations Of Machine Learning. The MIT Press
  * Pedregosa et al. (2011) Pedregosa F, Varoquaux G, Gramfort A, Michel V, Thirion B, Grisel O, Blondel M, Prettenhofer P, Weiss R, Dubourg V, Vanderplas J, Passos A, Cournapeau D, Brucher M, Perrot M, Duchesnay E (2011) Scikit-learn: Machine learning in Python. Journal of Machine Learning Research 12:2825–2830
  * Pele et al. (2013) Pele O, Taskar B, Globerson A, Werman M (2013) The pairwise piecewise-linear embedding for efficient non-linear classification. In: ICML
  * Perronnin et al. (2010) Perronnin F, Senchez J, et al. (2010) Large-scale image categorization with explicit data embedding. In: CVPR
  * Porikli and Ozkan (2011) Porikli F, Ozkan H (2011) Data driven frequency mapping for computationally scalable object detection. In: 2011 8th IEEE International Conference on Advanced Video and Signal Based Surveillance (AVSS), pp 30–35
  * Rahimi and Recht (2007) Rahimi A, Recht B (2007) Random features for large-scale kernel machines. NIPS
  * Rahimi and Recht (2009) Rahimi A, Recht B (2009) Weighted sums of random kitchen sinks: Replacing minimization with randomization in learning. In: Koller D, Schuurmans D, Bengio Y, Bottou L (eds) Advances in Neural Information Processing Systems 21, Curran Associates, Inc., pp 1313–1320
  * Saavedra et al. (2004) Saavedra E, Grauel A, Morton D (2004) Support vector machines and quad-trees applied to image compression. In: Proceedings of the 6th Nordic Signal Processing Symposium-NORSIG, Citeseer, vol 2004
  * Shawe-Taylor et al. (1998) Shawe-Taylor J, Bartlett PL, Williamson RC, Anthony M (1998) Structural risk minimization over data-dependent hierarchies. IEEE Transactions on Information Theory 44(5):1926–1940
  * Smola and Schökopf (2000) Smola AJ, Schökopf B (2000) Sparse greedy matrix approximation for machine learning. In: Proceedings of the Seventeenth International Conference on Machine Learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, ICML ’00, pp 911–918, URL http://dl.acm.org/citation.cfm?id=645529.657980
  * Tsang et al. (2005) Tsang IW, Kwok JT, Cheung PM (2005) Core vector machines: Fast svm training on very large data sets. Journal of Machine Learning Research 6(Apr):363–392
  * Tsang et al. (2007) Tsang IW, Kocsor A, Kwok JT (2007) Simpler core vector machines with enclosing balls. In: Proceedings of the 24th international conference on Machine learning, ACM, pp 911–918
  * Vedaldi and Zisserman (2012) Vedaldi A, Zisserman A (2012) Efficient additive kernels via explicit feature maps. PAMI
  * Vempati et al. (2010) Vempati S, Vedaldi A, Zisserman A, Jawahar CV (2010) Generalized RBF feature maps for efficient detection. In: BMVC, British Machine Vision Association, pp 1–11
  * Williams and Seeger (2000) Williams C, Seeger M (2000) The effect of the input density distribution on kernel-based classifiers. In: Proceedings of the 17th International Conference on Machine Learning, Morgan Kaufmann, pp 1159–1166
  * Williams and Seeger (2001) Williams CKI, Seeger M (2001) Using the nyström method to speed up kernel machines. In: Leen TK, Dietterich TG, Tresp V (eds) Advances in Neural Information Processing Systems 13, MIT Press, pp 682–688, URL http://papers.nips.cc/paper/1866-using-the-nystrom-method-to-speed-up-kernel-machines.pdf

##  Appendix A Hybrid PAC-compression bounds

In this section, we present a hybrid compression bound used in the derivation
of Theorem 4.2.

#### General theory.

It will be convenient to present our results in generality and then
specialize. Our notation will be in line with Hanneke and Kontorovich (2019).
Let $P$ be a distribution on $\mathcal{Z}$. We write
$Z_{[n]}=(Z_{1},\ldots,Z_{n})\sim P^{n}$ and, for $f\in[0,1]^{\mathcal{Z}}$,

$\displaystyle R(f,P):=\mathop{\mathbb{E}}_{Z\sim
P}f(Z),\qquad\hat{R}(f,Z_{[n]}):=\frac{1}{n}\sum_{i=1}^{n}f(Z_{i}).$

We write $\Delta_{n}(f)=\Delta_{n}(f,P,Z_{[n]}):=R(f,P)-\hat{R}(f,Z_{[n]})$
and our main object of interest will be

$\displaystyle\bar{\Delta}_{n}(\mathcal{F}):=\sup_{f\in\mathcal{F}}\Delta_{n}(f,P,Z_{[n]}),$
(14)

for $\mathcal{F}\subset[0,1]^{Z}$. The catch is that $\mathcal{F}$ may itself
be random, determined by the $Z_{[n]}$. We will distinguish
$\bar{\Delta}_{n}(\mathcal{F})$ from the more familiar object
$\bar{\Delta}_{n}^{\textrm{{\tiny{FIX}}}}(\mathcal{F})$, which is formally
defined as in (14), but with the additional stipulation that $\mathcal{F}$ be
a fixed function class, independent of $Z_{[n]}$.

For a fixed $k\in\mathbb{N}$, consider a fixed mapping
$\rho:\mathcal{Z}^{k}\mapsto\mathcal{F}_{k}\subset[0,1]^{Z}$. In words, $\rho$
maps $k$-tuples over $\mathcal{Z}$ into function classes over $\mathcal{Z}$.
This generalizes the notion of a decoding in a sample compression scheme,
where $\rho$ maps a $k$-tuple over $\mathcal{Z}$ into a single function
$f\in[0,1]^{\mathcal{Z}}$. Denote by $\mathcal{F}_{\rho}(Z_{[n]})$ the
collection of all functions constructable by $\rho$ on a given $Z_{[n]}$:

$\displaystyle\mathcal{F}_{\rho}(Z_{[n]})=\bigcup_{I\in{[n]\choose
k}}\rho(Z_{I}),$ (15)

where $[n]\choose k$ is the set of all $k$-subsets of $[n]$, and $Z_{I}$ is
the restriction of $Z_{[n]}$ to the index set $I$. 222 We consider, for
concreteness, permutation and repetition-invariant compression schemes; the
extension to general ones is straightforward. The only requisite change
consists of replacing $\cup_{I\in{[n]\choose k}}$ with $\cup_{I\in{[n]^{k}}}$
in (15).

A trivial application of the union bound yields

$\displaystyle\mathop{\mathbb{P}}\left(\bar{\Delta}_{n}(\mathcal{F}_{\rho}(Z_{[n]}))\geq\varepsilon\right)$
$\displaystyle\leq$ $\displaystyle{n\choose k}\max_{I\in{[n]\choose
k}}\mathop{\mathbb{P}}\left(\bar{\Delta}_{n}(\rho(Z_{I}))\geq\varepsilon\right).$

The key observation is that, conditioned on $Z_{I}$, the function class
$\mathcal{F}_{I}:=\rho(Z_{I})$ becomes deterministic and independent of
$Z_{J}$, where $J:=[n]\setminus I$. Thus,

$\displaystyle\mathop{\mathbb{P}}\left(\bar{\Delta}_{n}(\mathcal{F}_{I})\geq\varepsilon\right)$
$\displaystyle=$
$\displaystyle\mathop{\mathbb{E}}_{Z_{I}}\left[\mathop{\mathbb{P}}\left(\bar{\Delta}_{n}(\mathcal{F}_{I})\geq\varepsilon\,|\,Z_{I}\right)\right].$

Conditional on $Z_{I}$, we have, for a given $f\in\mathcal{F}_{I}$,

$\displaystyle\Delta_{n}(f,P,Z_{[n]})=R(f,P)-\hat{R}(f,Z_{[n]})$
$\displaystyle=$ $\displaystyle\mathop{\mathbb{E}}_{Z\sim
P}f(Z)-\frac{1}{n}\sum_{i=1}^{n}f(Z_{i})$ $\displaystyle=$
$\displaystyle\mathop{\mathbb{E}}f(Z)-\frac{1}{n}\sum_{i\in
J}f(Z_{i})-\frac{1}{n}\sum_{i\in I}f(Z_{i})$ $\displaystyle\leq$
$\displaystyle\mathop{\mathbb{E}}f(Z)-\frac{1}{n}\sum_{i\in J}f(Z_{i})$
$\displaystyle\leq$
$\displaystyle\mathop{\mathbb{E}}f(Z)-\frac{1}{|J|}\sum_{i\in J}f(Z_{i})$
$\displaystyle=$ $\displaystyle
R(f,P)-\hat{R}(f,Z_{J})=\Delta_{n-k}(f,P,Z_{J}),$

where $f(\cdot)\in[0,1]$ and $|J|=n-k$ were used. It follows that

$\displaystyle\bar{\Delta}_{n}(\mathcal{F}_{I})\leq\bar{\Delta}_{n-k}^{\textrm{{\tiny{FIX}}}}(\mathcal{F}_{I}).$

We now state the main result of this section:

###### Theorem A.1

$\displaystyle\mathop{\mathbb{P}}\left(\bar{\Delta}_{n}(\mathcal{F}_{\rho}(Z_{[n]}))\geq\varepsilon\right)$
$\displaystyle\leq$ $\displaystyle{n\choose k}\max_{I\in{[n]\choose
k}}\mathop{\mathbb{P}}\left(\bar{\Delta}_{n-k}^{\textrm{{\tiny{FIX}}}}(\mathcal{F}_{I})\geq\varepsilon\right).$
(16)

To apply (16) to examples of interest, let us compute the right-hand side of
the bound for some function classes.

#### Example: VC classes.

In our first example, suppose that $\rho$ maps $k$-tuples of $\mathcal{Z}$ to
binary concept classes — which might well be different for each $k$-tuple — of
VC-dimension at most $d$. More precisely, we take
$\mathcal{Z}=\mathcal{X}\times\left\\{0,1\right\\}$, where $\mathcal{X}$ is an
instance space. Let
$\mathcal{H}=\mathcal{H}_{z}\subseteq\left\\{0,1\right\\}^{\mathcal{X}}$ be a
concept class defined by the $k$-tuple $z\in\mathcal{Z}^{k}$, with VC-
dimension $d$. Define $\mathcal{F}\subseteq\left\\{0,1\right\\}^{\mathcal{Z}}$
to be its associated loss class:

$\displaystyle\mathcal{F}=\left\\{f_{h}:(x,y)\mapsto\boldsymbol{\mathbbm{1}}_{\left\\{h(x)\neq
y\right\\}};h\in\mathcal{H}\right\\}.$

We call this setting a hybrid $(k,d)$ VC sample-compression scheme. It is
well-known (see, e.g., (Anthony and Bartlett, 1999, Theorem 4.9)) that

$\displaystyle\mathop{\mathbb{E}}[\bar{\Delta}_{n}^{\textrm{{\tiny{FIX}}}}(\mathcal{F})]\leq
c\sqrt{{d}/{n}},$ (17)

where $c>0$ is a universal constant (for concreteness, we may take $c=144$)333
https://www.cs.bgu.ac.il/~asml162/wiki.files/dudley-pollard.pdf . Further,
$\bar{\Delta}_{n-k}^{\textrm{{\tiny{FIX}}}}(\mathcal{F})$ is known to be
concentrated about its mean (see, e.g., (Mohri et al., 2012, Theorem 3.1)):

$\displaystyle\mathop{\mathbb{P}}\left(\bar{\Delta}_{n}^{\textrm{{\tiny{FIX}}}}(\mathcal{F})\geq\mathop{\mathbb{E}}[\bar{\Delta}_{n}^{\textrm{{\tiny{FIX}}}}(\mathcal{F})]+\varepsilon\right)\leq\exp(-2n\varepsilon^{2}).$
(18)

Combining (16), (17), and (18), we conclude:

###### Corollary 1

In a hybrid $(k,d)$ VC sample compression scheme, on a sample of size $n$, a
learner’s sample error $\widehat{\operatorname{err}}(\hat{h}_{n})$ and
generalization error $\operatorname{err}(\hat{h}_{n})$ satisfy

$\displaystyle\operatorname{err}(\hat{h}_{n})\leq\widehat{\operatorname{err}}(\hat{h}_{n})+c\sqrt{\frac{d}{n-k}}+\sqrt{\frac{\log[\delta^{-1}{n\choose
k}]}{2(n-k)}}$

with probability at least $1-\delta$.

#### Example: Margin classes.

Here, we take $\mathcal{X}$ to be an abstract set,
$\mathcal{Y}=\left\\{-1,1\right\\}$,
$\mathcal{Z}=\mathcal{X}\times\mathcal{Y}$, and define

$\displaystyle\tilde{\mathcal{H}}=\left\\{h_{w}:\mathcal{X}\ni x\mapsto
w\cdot\Psi(x);\left\|w\right\|\leq 1\right\\},$

where $\Psi(x)=\Psi_{z}(x)$ is a map from $\mathcal{X}$ to $\mathbb{R}^{N}$
determined by some $k$-tuple $z\in\mathcal{Z}$, with
$\left\|\Psi_{z}(\cdot)\right\|\leq 1$. Associate to $\tilde{\mathcal{H}}$ the
$\gamma$-margin loss class

$\displaystyle\mathcal{F}_{\gamma}=\left\\{f_{h}:\mathcal{X}\times\left\\{-1,1\right\\}\ni(x,y)\mapsto\Phi_{\gamma}(yh(x));h\in\tilde{\mathcal{H}}\right\\},$

where $\Phi_{\gamma}(t)=\min(0,\max(1,1-t/\gamma))$. We refer to this setting
as a hybrid $(k,\gamma)$ margin sample compression scheme. It is a standard
fact (see, e.g., (Mohri et al., 2012, Theorem 4.4)) that

$\displaystyle\mathop{\mathbb{P}}\left(\bar{\Delta}_{n}^{\textrm{{\tiny{FIX}}}}(\mathcal{F}_{\gamma})\geq\frac{2}{\gamma\sqrt{n}}+\varepsilon\right)\leq\exp(-2n\varepsilon^{2}).$
(19)

Combining (16), (19), and a standard stratification argument (see (Mohri et
al., 2012, Theorem 4.5)), we obtain the following result. Fix a map
$\rho:\mathcal{Z}^{k}\to\Psi(\cdot)$. Given a sample
$Z_{[n]}=(X_{i},Y_{i})_{i\in[n]}$ drawn iid, the learner chooses some $k$
examples to define the random mapping $\Psi_{z}:\mathcal{X}\to\mathbb{R}^{N}$.
Having mapped the sample to $R^{N}$, he runs SVM and obtains a hyperplane $w$.

###### Corollary 2

With probability at least $1-\delta$, we have

$\displaystyle\mathop{\mathbb{E}}_{(X,Y)}[\operatorname{sgn}(Yw\cdot\Psi(X))\leq
0\,|\,Z_{[n]}]$ $\displaystyle\leq$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\max(0,1-Y_{i}w\cdot\Psi(X_{i}))+\frac{4}{\left\|w\right\|\sqrt{n-k}}$
$\displaystyle+$
$\displaystyle\sqrt{\frac{\log\log_{2}\frac{2}{\left\|w\right\|}}{n-k}}+\sqrt{\frac{\log(2{n\choose
k}/\delta)}{2(n-k)}}.$