# Dimension Free Generalization Bounds for Non Linear Metric Learning

Mark Kozdoba1
<EMAIL_ADDRESS>Shie Mannor1
<EMAIL_ADDRESS>
( 1Technion, Israel Institute of Technology )

###### Abstract

In this work we study generalization guarantees for the metric learning
problem, where the metric is induced by a neural network type embedding of the
data. Specifically, we provide uniform generalization bounds for two regimes –
the sparse regime, and a non-sparse regime which we term _bounded
amplification_. The sparse regime bounds correspond to situations where
$\ell_{1}$-type norms of the parameters are small. Similarly to the situation
in classification, solutions satisfying such bounds can be obtained by an
appropriate regularization of the problem. On the other hand, unregularized
SGD optimization of a metric learning loss typically does not produce sparse
solutions. We show that despite this lack of sparsity, by relying on a
different, new property of the solutions, it is still possible to provide
dimension free generalization guarantees. Consequently, these bounds can
explain generalization in non sparse real experimental situations. We
illustrate the studied phenomena on the MNIST and 20newsgroups datasets.

##  1 Introduction

Metric Learning, [Bellet et al., 2015], is the problem of finding a metric
$\rho$ on the space of features, such that $\rho$ reflects some semantic
properties of a given task. Generally, the input can be thought of as a set of
labeled pairs $\left\\{((x_{i},x^{\prime}_{i}),y_{i})\right\\}_{i=1}^{n}$,
where $x_{i},x^{\prime}_{i}\in\mathbb{R}^{d}$ are the features, and $y_{i}$ is
the label, indicating whether $x_{i}$ and $x^{\prime}_{i}$ should be close in
the metric or far apart. For instance, in face identification, [Schroff et
al., 2015], features $x_{i}$ and $x^{\prime}_{i}$ corresponding to the same
face should be close in $\rho$, while different faces should be far apart.

Note that the above metric learning formulation is fairly general and one can
convert supervised clustering, or even standard classification problems into
metric learning simply by setting $y_{i}=1$ if $x_{i}$ and $x^{\prime}_{i}$
have the same original label and $y_{i}=0$ otherwise [Davis et al., 2007,
Weinberger and Saul, 2009, Cao et al., 2016, Khosla et al., 2020, Chicco,
2020].

The metric $\rho$ is typically assumed to be the Euclidean metric taken after
a linear or non-linear _embedding_ of the features. That is, we consider a
parametric family $\mathcal{F}^{*}$ of embeddings into a $k$-dimensional
space, $f^{*}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{k}$, and set 111Note that
$\rho$ in (1) is not strictly a metric. Nevertheless, this terminology is
common.

$\rho(x,x^{\prime})=\rho_{k,f^{*}}(x,x^{\prime})=\frac{1}{k}\left\|f^{*}(x)-f^{*}(x^{\prime})\right\|_{2}^{2}.$
(1)

(a) Raw features, after normalization and 500 dim. PCA.

(b) Learned embedding, k=50, test set.

Figure 1:  tSNE plot of the 20newsgroup data, restricted to the first 10
labels. Points are colored according to the label.

As an example, Figure 1 shows tSNE plots, [Maaten and Hinton, 2008], of the
classical 20newsgroups dataset. Figure 1(a) was generated using the regular
bag of words representation of the data (see Section 6 for additional details)
while Figure 1(b) was generated by applying tSNE to an embedding of the data
(of the form (3) below) learned by minimizing a loss based on labels, as
described above. Clearly, there is no discernible relation between the label
and the metric in the raw representation, but there is a strong relation in
the learned metric. One can also obtain similar conclusions, and quantify
them, by, for instance, replacing tSNE with spectral clustering.

The uniform _generalization_ problem for metric learning is the following:
Given a family of embeddings $\mathcal{F}^{*}$, provide bounds, that hold
uniformly for all $f^{*}\in\mathcal{F}^{*}$, on the difference between the
expected value of the loss and the average value of the loss on the train set;
see Section 2 for a formal definition. Such bounds guarantee, for instance,
that the train set would not be overfitted. Given a family of embeddings
$\mathcal{F}^{*}$, consider the family $\mathcal{F}$ of functions
$f:\mathbb{R}^{d}\times\mathbb{R}^{d}\rightarrow\mathbb{R}$ of the form

$\mathcal{F}=\left\\{f(x,x^{\prime})=\rho_{k,f^{*}}(x,x^{\prime})\hskip
5.69054pt|\hskip 5.69054ptf^{*}\in\mathcal{F}^{*}\right\\}.$ (2)

We refer to these as the distance functions, which map a pair of features into
their distance after the embedding. Well known arguments imply that one can
obtain generalization bounds for $\mathcal{F}^{*}$ by providing upper bounds
on the _Rademacher complexity_ $\mathfrak{R}_{n}\left(\mathcal{F}\right)$ of
the family of the scalar functions $\mathcal{F}$. Therefore in what follows,
we discuss directly the upper bounds on
$\mathfrak{R}_{n}\left(\mathcal{F}\right)$ for various families
$\mathcal{F}^{*}$. We refer to Sections 2 and 4 for formal definitions and
details on the relation between
$\mathcal{F}^{*}$,$\mathcal{F}$,$\mathfrak{R}_{n}\left(\mathcal{F}\right)$,
and generalization bounds.

###  1.1 Sparsity Based Bounds

In this paper our goal is to provide generalization bounds for neural network
type non-linear embeddings $f^{*}$. Specifically, we will be interested in
embeddings $f^{*}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{k}$ of the form

$f^{*}(x)=\phi(A^{t}x)$ (3)

where $A\in\mathbb{R}^{d\times k}$ is a matrix and
$\phi:\mathbb{R}\rightarrow\mathbb{R}$ is a Lipschitz non-linearity which acts
on $A^{t}x$ coordinatewise. Equivalently, these embeddings are given by a
single layer of a neural network. We note that the single layer case is the
essential hard case for the metric learning problem. It is interesting in its
own right, and moreover, multi-layer guarantees can easily be obtained by
combining the single layer case with the methods used in the derivation of the
existing neural network bounds. Additional details are provided in Remark 6.
In view of this, in most parts of this paper we will concentrate on the single
layer case.

Let $\left\|A\right\|_{op}$ denote the spectral norm, and set
$\left\|A\right\|_{2,1}=\sum_{i=1}^{k}\left\|A_{\cdot i}\right\|_{2}$, where
$A_{\cdot i}$ is the $i$-th column of $A$. Let $\mathcal{F}^{*}$ be the set of
embedding of the form (3) induced by some set of matrices $\mathcal{G}$. In
what follows we identify $\mathcal{G}$ and $\mathcal{F}^{*}$ and refer to
$\mathcal{F}^{*}$ directly as the set of matrices, where the embeddings are
assumed to be of the form $(\ref{eq:non_lin_emebdding_one_layer_def})$. We
further assume that input feature norms are bounded by some $b>0$,
$\left\|x\right\|_{2}\leq b$. Recall that $n$ is the number of samples.

Our first result is the following generalization bound (up to constants and
logarithmic terms):

$\mathfrak{R}_{n}\left(\mathcal{F}\right)\leq\frac{b^{2}\left\|\phi\right\|^{2}_{Lip}\sup_{A\in\mathcal{F}^{*}}\left\|A\right\|_{op}\sup_{A\in\mathcal{F}^{*}}\left\|A\right\|_{2,1}}{k\sqrt{n}}.$
(4)

The full statement and proof of this result are given as Theorem 1. This bound
is the direct analog, in the metric learning setting, of the strongest
currently known uniform bounds for neural network classification, [Bartlett et
al., 2017], which are also formulated in terms of $\left\|\cdot\right\|_{op}$
and $\left\|\cdot\right\|_{2,1}$ norms. Bounds using these norms may generally
be regarded as _sparsity_ type bounds – if we control the sum of the norms of
coordinate functionals, then we control generalization. In particular, this
bound will be small iff only a small number of output coordinate functionals
(i.e. columns of $A$) have large norms. This is similar to the standard
$\ell_{1}$ regularized logistic regression, where we want only a small number
of coefficients to be large.

###  1.2 Bounded Amplification Based Bounds

If the $\left\|A\right\|_{2,1}$ is forced to be small, for instance by adding
an appropriate regularization term to the loss, then the learned $A$ will be
sparse and (4) may explain generailzation. However, solutions obtained by
stochastic gradient descent without regularization are not sparse. We
illustrate this in Section 6 using standard datasets. In these experiments an
embedding is learned by minimizing the loss with SGD without any
regularization (or at least, without $\left\|A\right\|_{2,1}$ regularization),
and we observe the behavior of the norms for a range of values of $k$. We find
that on the one hand, even for large values of $k$ the generalization gap
stays bounded, there is no overfitting. On the other hand, for the learned
matrices $A$ the norm $\left\|A\right\|_{2,1}$ grows linearly with $k$ while
$\left\|\cdot\right\|_{op}$ grows as $\sqrt{k}$. This in particular means that
the left handside of (4) grows as $\sqrt{k}$, which suggests that it can not
explain the observed generalization.

Consequently, to explain the above generalization, we introduce a different
bound. Denote $\left\|A\right\|_{2,\infty}=\max_{i\leq k}\left\|A_{\cdot
i}\right\|_{2}$. Then (again, up to logarithmic terms) we have:

$\mathfrak{R}_{n}\left(\mathcal{F}\right)\leq\frac{b^{2}\sup_{A\in\mathcal{F}^{*}}\left\|A\right\|_{2,\infty}^{2}}{\sqrt{n}}.$
(5)

This will be shown in Theorem 4. In the experiments we observe that
$\left\|A\right\|_{2,\infty}$ remains roughly constant as a function of $k$,
and therefore this bound does explain the generalization. Even more
importantly, however, the bound (5) is remarkable because there is no sparsity
control term for columns and yet it is still _dimension free_. That is, the
feature and embedding dimensions, $d$ and $k$, do not enter the bound.

Put differently, typically sparsity implies generalization because while the
problem may have many parameters, only few of them will be non-zero at each
instance of the problem, and thus “effective” number of parameters is low,
[Hastie et al., 2015, Bartlett et al., 2017, Zhou et al., 2019]. In contrast,
in (5), all $k$ columns can have the same non zero Euclidean norm $a$, the
“effective” number of parameters can be arbitrarily high, and yet the bound
will not deteriorate when the number of samples $n$ is fixed and $k$ is
growing. We refer to situations where only $\left\|A\right\|_{2,\infty}$ is
bounded as the _bounded amplification_ regime, as distinguished from the
sparse regime. The boundedness here refers to the fact that each column
individually still should be $\ell_{2}$ bounded.

It is important to note that the normalization by $k$ in (1) is crucial to the
fact that (5) is dimension free. In Remark 7 we discus in detail why this is
an appropriate normalization for this case. It is also worth noting that among
the bounds (4) and (5) none is stronger than the other, i.e., it is not true
that (4) implies (5) or vice versa. Rather, they apply to genuinely different
types of embeddings $f^{*}$, those that minimize the
$\left\|\cdot\right\|_{2,1}$-regularized loss, and those that minimize the
unregularized one.

###  1.3 Methods

We now briefly describe the ideas underlying the proofs. To prove (4) we take
the classical approach of bounding the covering numbers of the set of
$\left\|\cdot\right\|_{2,1}$ bounded matrices, using an estimate from
[Bartlett et al., 2017], which in turn is an extension of estimates in [Zhang,
2002], [Bartlett, 1998]. The Rademacher bound then follows from the Dudley
entropy bound. However, this method does not seem to yield (5), and provides
bounds that are off by a $\sqrt{k}$ factor. Thus, to prove (5) we take a
different approach.

We give two proofs for (5), both of which exploit the particular structure of
the metric (1) as an average over the coordinates. Equivalently, the distance
$\rho_{k,f}$ can be viewed as a voting outcome by an ensemble of individual
coordinates. The first argument is based on the sub-additivity of Rademacher
complexities and makes a direct use of the average structure as above. The
second argument is a dimension reduction scheme. This argument gives a
somewhat weaker, although still dimension independent result, but has the
advantage of making it much clearer _why_ there is dimension independent
generalization. We also believe this argument has greater potential in
generalizing to other situations. This dimension reduction was inspired by
[Schapire et al., 1998], where a related approach was used to analyze ensemble
learning.

###  1.4 Contributions

To conclude this Section we summarize the contributions of this work: (i) For
metric learning with non linear embeddings, we prove generalization bounds
which depend only on the norms $\left\|\cdot\right\|_{2,1}$,
$\left\|\cdot\right\|_{op}$ of the embedding matrix, similarly to the recent
neural network classification bounds. (ii) We introduce a new type of bounds,
the bounded amplification type bounds, with dependence only on the
$\left\|\cdot\right\|_{2,\infty}$ norm. Such bounds have not been studied
before, in metric learning, or in statistical learning theory in general. The
methods of proof here are also new. (iii) We observe empirically that the
above bounded amplification regime of matrix weights occurs naturally in basic
experiments on standard datasets. Our new bounds therefore can explain, in
standard situations, dimension independence that can not be explained by the
more common types of bounds.

The rest of this paper is organized as follows: In Section 2 we overview the
necessary background on metric learning and generalization. Literature and
related work are discussed in Section 3. In Section 4 we provide the notation
required for the formal discussion of the results. Section 5 contains the
statements of the results and overviews of the proofs. Some of full proofs are
deferred to the Supplementary Material due to space constraints. Experiments
are described in Section 6. In Section 7 we conclude the paper and discuss
future work.

##  2 Metric Learning Background

As discussed in Section 1, we assume that the training data is given as a set
$\left\\{((x_{i},x^{\prime}_{i}),y_{i})\right\\}_{i=1}^{n}$ of labeled feature
pairs, which we assume to be sampled independently form some distribution
$\mathcal{D}$ on $\mathbb{R}^{d}\times\mathbb{R}^{d}\times Y$, where $Y$ is
some set of label values. It is usually sufficeint to take
$Y=\left\\{0,1\right\\}$. Note that there may be dependence _within_ the pair,
i.e. $x^{\prime}_{i}$ may depend on $x_{i}$.

The quality of the embedding $f^{*}$ on a data point $((x,x^{\prime}),y)$ is
measured via a _loss function_ $\ell$, which usually depends on
$((x,x^{\prime}),y)$ only through the metric $\rho_{k,f^{*}}$. That is, we
assume that there is a fixed function $\ell:\mathbb{R}\times
Y\rightarrow[0,1]$, such that the loss of $f^{*}\in\mathcal{F}^{*}$ on a data
point $((x,x^{\prime}),y)$ is given by
$L_{f^{*}}((x,x^{\prime}),y)=\ell(\rho_{k,f^{*}}(x_{i},x_{i}^{\prime}),y_{i})$.
A typical example of a loss $\ell$ is the following version of the margin
loss:

$\ell_{S,D}^{\lambda}(\rho,y)=\begin{cases}\min\left(1,\lambda\cdot
ReLU\left(\rho-S\right)\right)&\text{ if }y=1\\\ \min\left(1,\lambda\cdot
ReLU\left(D-\rho\right)\right)&\text{ otherwise},\end{cases}$

where $ReLU(x)=\max\left(0,x\right)$. As discussed in Section 1, this loss
embodies the principle that $(x,x^{\prime})$ should be close iff $y=1$, by
penalizing distances above $S$ when $y=1$ and penalizing distances below $D$
otherwise.

The overall loss on the data, or the empirical risk, is given by

$\hat{R}_{f^{*}}=\frac{1}{n}\sum_{i=1}^{n}L_{f^{*}}((x_{i},x_{i}^{\prime}),y_{i}).$
(6)

The expected risk is given by
$R_{f^{*}}=\mathbb{E}_{((x,x^{\prime}),y)\sim\mathcal{D}}L_{f^{*}}((x,x^{\prime}),y)$.
The uniform generalization problem of metric learning is similar to the
generalization problem of classification: One is interested in conditions on
the family $\mathcal{F}^{*}$ under which the gap between expected and
empirical risks, $R_{f^{*}}-\hat{R}_{f^{*}}$, is small for all
$f^{*}\in\mathcal{F}^{*}$.

Finally, since $\left\\{((x_{i},x^{\prime}_{i}),y_{i})\right\\}_{i=1}^{n}$ are
independent, standard results imply that to control the uniform generalization
bounds of the risk, it is sufficient to control the Rademacher complexity of
the family $\mathcal{F}$ of distance value functions induced by
$\mathcal{F}^{*}$, as defined in (2). Specifically, we have that (see [Mohri
et al., 2018] Theorem 3.3 and Lemma 5.7) ,

$\sup_{f\in\mathcal{F}}R_{f^{*}}-\hat{R}_{f^{*}}\leq
2\left\|\ell\right\|_{Lip}\mathfrak{R}_{n}\left(\mathcal{F}\right)+\sqrt{\frac{\log\delta^{-1}}{2n}}$

holds with probability at least $1-\delta$. Here
$\mathfrak{R}_{n}\left(\mathcal{F}\right)$ is the Rademacher complexity of
$\mathcal{F}$ and $\left\|\ell\right\|_{Lip}$ is the Lipschitz constant of
$\ell$ as a function of its first coordinate.

##  3 Literature

A general survey of the field of metric learning can be found in [Bellet et
al., 2015]. See also [Chicco, 2020] for a survey of recent applications in
deep learning contexts. In these situations, the metric learning loss is
sometimes referred to as a Siamese network.

Up to now, generalization guarantees in metric learning were only studied in
the _linear_ setting, i.e. for embeddings of the form (3) where $\phi(x)=x$.
In particular, all literature cited in this Section deals with the linear
case.

As discussed in Sections 1 and 2, in this paper we use the formal setting
introduced in [Verma and Branson, 2015], where we assume that the data comes
as a set of iid feature pairs with a label per pair,
$((x_{i},x_{i}^{\prime}),y_{i})_{i=1}^{n}$. In this setting, the empirical
risk is given by (6). In the special case where the data comes with a label
per feature, $(x_{i},l_{i})_{i=1}^{n}$, one can use an alternative notion of
empirical risk, given by

$\tilde{R}_{f}=\frac{1}{n(n-1)}\sum_{i=1}^{n}\sum_{j\neq
i}L_{f}\left((x_{i},x_{j}),\mathbbm{1}_{\left\\{l_{i}\neq
l_{j}\right\\}}\right),$ (7)

which is viewed as a second order U-statistic, see [Cao et al., 2016]. That
is, instead of considering the input as a set of independently sampled pairs,
which can be obtained from the $(x_{i},l_{i})_{i=1}^{n}$ by, for instance,
creating pairs out of consecutive samples, in (7) one considers all possible
pairs. On one hand, compared to the risk $\hat{R}_{f}$ defined by (6), for
small datasets $\tilde{R}_{f}$ might make a somewhat better use of the data.
On the other hand, $\tilde{R}_{f}$ is less general, since the data does not
necessarily have to be generated by the label-per-feature setting, and
moreover, even evaluating (7) may be computationally difficult since the
number of terms in the sum is quadratic in dataset size. In practice, the
empirical loss used is somewhere between $\hat{R}_{f}$ and $\tilde{R}_{f}$.

The generalization setting considered here is that of the _uniform
generalization bounds_ , see [Mohri et al., 2018]. Alternatively, in [Wang et
al., 2019], [Lei et al., 2020], the linear case of metric learning was studied
in the framework of algorithmic stability ([Bousquet and Elisseeff, 2002],
[Feldman and Vondrak, 2019], [Bousquet et al., 2020]). In these works,
stability, and consequently generalization bounds, were obtained for an
appropriately regularized empirical risk minimization (ERM) procedure. We note
that these methods rely strongly on the (uniform) convexity of the underlying
problem, and are unlikely to be generalized to non linear settings. In [Bellet
and Habrard, 2015],[Christmann and Zhou, 2016], linear metric learning was
studied in the framework of algorithmic robustness, [Xu and Mannor, 2012].

Finally, uniform bounds for the linear case were studied in [Verma and
Branson, 2015], and similar results for the version of risk as in (7) were
obtained in [Cao et al., 2016]. In particular it was shown in [Verma and
Branson, 2015] that

$\mathfrak{R}_{n}\left(\mathcal{F}\right)\leq\frac{b^{2}\sup_{A\in\mathcal{F}^{*}}\left\|AA^{t}\right\|_{F}}{k\sqrt{n}}.$
(8)

One can show that both (4) and (5) can be derived from this bound using known
matrix norm inequalities. The bound (8) itself is derived in [Verma and
Branson, 2015] using a relatively short elegant argument involving only the
Cauchy Schwartz inequality. However, this argument can be applied only when
$\phi$ is the identity. Similarly to the situation in classification, for the
non-linear settings other arguments are required.

##  4 Notation

For a vector $v=(v_{1},\ldots,v_{m})\in\mathbb{R}^{m}$, the $\ell_{p}$ norm is
denoted by
$\left\|v\right\|_{p}=\left(\sum_{j=1}^{m}\left|v_{j}\right|^{p}\right)^{1/p}$.
For a matrix $A\in R^{d\times k}$, and $1\leq p,s\leq\infty$, denote
$\left\|A\right\|_{p,s}=\left\|\left(\left\|A_{\cdot
1}\right\|_{p},\ldots,\left\|A_{\cdot k}\right\|_{p}\right)\right\|_{s}$. That
is, one first computes the $p$-th norm of the columns and then the $s$-th norm
of the vector of these norms. Note that
$\left\|A\right\|_{2,2}=\left\|A\right\|_{2}$ is the Frobenius norm. Denote by
$\left\|A\right\|_{op}$ the spectral norm of $A$. Throughout
$\phi:\mathbb{R}\rightarrow\mathbb{R}$ will denote the non-linearity, with
Lipschitz constant $\left\|\phi\right\|_{Lip}$ and such that $\phi(0)=0$.

The $\varepsilon$ covering number of a set $\mathcal{A}\subset\mathbb{R}^{n}$,
denoted $\mathcal{N}(\mathcal{A},\varepsilon)$ is the minimal size of a set
$\mathcal{B}\subset\mathcal{A}$ such that for every $x\in\mathcal{A}$ there is
$y\in\mathcal{B}$ s.t. $\left\|x-y\right\|_{2}\leq\varepsilon$. The Rademacher
complexity of a set $\mathcal{F}\subset\mathbb{R}^{n}$ is defined by

$\mathfrak{R}\left(\mathcal{F}\right)=\frac{1}{n}\mathbb{E}_{\varepsilon}\sup_{f\in\mathcal{F}}\sum_{i=1}^{n}\varepsilon_{i}f_{i}$
(9)

where $\varepsilon_{i}$ are independent Bernoulli variables with
$\mathbb{P}\left(\varepsilon_{i}=1\right)=\mathbb{P}\left(\varepsilon_{i}=-1\right)=\frac{1}{2}$.
If $\mathcal{F}$ is a family of functions rather than a subset of
$\mathbb{R}^{n}$, as in $(\ref{eq:mcF_formal_def})$, then we set
$\mathfrak{R}_{n}\left(\mathcal{F}\right):=\mathfrak{R}\left(\mathcal{F}_{|x,x^{\prime}}\right)$
where $\mathcal{F}_{|x,x^{\prime}}\subset\mathbb{R}^{n}$ is the restriction of
$\mathcal{F}$ to the training set (see also Section 5.1).

We use the standard notation $O(\cdot)$ and $\Omega(\cdot)$ for upper bounded
and equivalent, respectively, up to absolute constants. $\overline{O}(\cdot)$
will denote upper boundedness up to absolute constants and logarithmic terms.

##  5 Results

In Section 5.1 we sate the sparse regime bound, Theorem 1, and provide an
overview of the proof. The full proof is given in Supplementary Material
Section A. We also derive Corollary 3, which is a version of the bounded
amplification bound, but with an additional $\sqrt{k}$ factor. Both proofs of
the non sparse bound apply Corollary 3 with smaller values of $k$.

In Section 5.2 we state the bounded amplification result, Theorem 4. As
discussed in Section 1.3, we give two proofs for Theorem 4, the first of which
is given in Supplementary Material Section C. We then discuss the dimension
reduction argument and prove the fundamental underlying approximation result,
Lemma 5. The derivation of the Rademacher complexity bound from Lemma 5 is
given in Supplementary Material Section D.

###  5.1 Sparse Case

We use the setting described in Section 1. Assume that we are given feature
pairs
$\left\\{(x_{i},x^{\prime}_{i})\right\\}_{i=1}^{n}\in\mathbb{R}^{d}\times\mathbb{R}^{d}$,
where each pair was sampled independently from some distribution on such
pairs. Note that there may be dependence inside pairs, i.e. $x_{i}$ may depend
on $x^{\prime}_{i}$, only the pairs themselves are assumed independent. These
inputs are organized as two matrices, $X,X^{\prime}\in\mathbb{R}^{n\times d}$,
with rows $x_{i}$ and $x^{\prime}_{i}$ respectively.

Define a shorthand for the normalized squared Euclidean norm on
$\mathbb{R}^{k}$,
$\zeta_{k}(x,x^{\prime})=\frac{1}{k}\left\|x-x^{\prime}\right\|_{2}^{2}$ for
$x,x^{\prime}\in\mathbb{R}^{k}$. Let $\mathcal{G}\subset\mathbb{R}^{d\times
k}$ be a set of matrices. We will be interested in the family of vectors

$\displaystyle\mathcal{F}_{k}(\mathcal{G})$
$\displaystyle=\mathcal{F}_{X,X^{\prime},k}(\mathcal{G})$
$\displaystyle=\left\\{\left(\zeta_{k}(\phi(A^{t}x_{i}),\phi(A^{t}x^{\prime}_{i})\right)_{i=1}^{n}\hskip
5.69054pt|\hskip 5.69054ptA\in\mathcal{G}\right\\}\subset\mathbb{R}^{n},$

for various sets $\mathcal{G}$ of matrices. In words,
$\mathcal{F}_{k}(\mathcal{G})$ is the set of distance functions
$f(x,x^{\prime})=\zeta_{k}(\phi(A^{t}x),\phi(A^{t}x^{\prime})$ induced by
$A\in\mathcal{G}$, restricted to the input
$\left\\{(x_{i},x^{\prime}_{i})\right\\}_{i=1}^{n}$. As discussed in Section
2, bounds on $\mathfrak{R}\left(\mathcal{F}_{k}(\mathcal{G})\right)$ imply
generalization bounds for metric learning with matrices in $\mathcal{G}$.

######  Theorem 1.

Given $a,a^{\prime}>0$, set

$\mathcal{J}^{k}_{a,a^{\prime}}=\left\\{A\hskip 5.69054pt|\hskip
5.69054ptA\in\mathbb{R}^{d\times k},\left\|A\right\|_{2,1}\leq
a,\left\|A\right\|_{op}\leq a^{\prime}\right\\}.$ (10)

Assume that $\left\|x_{i}\right\|\leq b$ for all $i\leq n$. Then

$\mathfrak{R}\left(\mathcal{F}_{k}(\mathcal{J}^{k}_{a,a^{\prime}})\right)\leq\overline{O}\left(\frac{1}{n}+\frac{aa^{\prime}b^{2}\left\|\phi\right\|^{2}_{Lip}}{k\sqrt{n}}\right).$
(11)

We now briefly sketch the proof of Theorem 1. The full proof is given in
Supplementary Material Section A. As discussed in Section 1.3, to prove
Theorem 1, we bound the covering numbers
$\mathcal{N}(\mathcal{F}_{k}(\mathcal{J}^{k}_{a,a^{\prime}}),\varepsilon)$.
The Rademacher complexity bound then follows using standard considerations,
via the Dudley entropy integral bound.

To bound
$\mathcal{N}(\mathcal{F}_{k}(\mathcal{J}^{k}_{a,a^{\prime}}),\varepsilon)$ we
will use following covering lemma from [Bartlett et al., 2017], stated for the
case of $\left\|A\right\|_{2,1}$ norms.

######  Lemma 2 ([Bartlett et al., 2017]).

For any $a>0$, set

$\mathcal{J}^{k}_{a}=\left\\{A\hskip 5.69054pt|\hskip
5.69054ptA\in\mathbb{R}^{d\times k},\left\|A\right\|_{2,1}\leq
a\right\\}\subset\mathbb{R}^{d\times k},$ (12)

and for any $X\in\mathbb{R}^{n\times d}$ and a set of matrices
$\mathcal{G}\subset\mathbb{R}^{d\times k}$ set $X\mathcal{G}=\left\\{XA\hskip
5.69054pt|\hskip 5.69054ptA\in\mathcal{G}\right\\}\subset\mathbb{R}^{n\times
k}$. Then for any $\varepsilon>0$,

$\log\mathcal{N}(X\mathcal{J}^{k}_{a},\varepsilon)\leq\frac{a^{2}\left\|X\right\|_{2}^{2}}{\varepsilon^{2}}\log\left(2dk\right).$
(13)

The proof of this Lemma in [Bartlett et al., 2017] is based on Maurey’s Lemma,
similarly to the arguments in [Zhang, 2002],[Bartlett, 1998]. We note that one
can instead directly estimate the supremum of the Rademacher process indexed
by $X\mathcal{J}_{a}^{k}$. Then Sudakov minoration, [Vershynin, 2018], would
yield a slight improvement upon (13), with no $d$ dependence inside the
logarithm.

Next, define a set of $n\times 2k$ matrices $\mathcal{Z}$ by
$\mathcal{Z}=\left\\{(XA,X^{\prime}A)\hskip 5.69054pt|\hskip
5.69054ptA\in\mathcal{J}_{a,a^{\prime}}^{k}\right\\}\subset\mathbb{R}^{n\times
2k}$. Let $\phi\mathcal{Z}:=\left\\{\phi(z)\hskip 5.69054pt|\hskip
5.69054ptz\in\mathcal{Z}\right\\}$ where $\phi$ is applied coordinatewise, and
let $\hat{\zeta_{k}}:\mathbb{R}^{d\times 2k}\rightarrow\mathbb{R}^{n}$ be the
mapping that applies $\zeta_{k}$ to the rows of elements in
$\mathbb{R}^{d\times 2k}$. Observe that by definition,
$\mathcal{F}_{k}(\mathcal{J}^{k}_{a,a^{\prime}})=\hat{\zeta_{k}}\left(\phi\mathcal{Z}\right)$.
Now, using Lemma 2, we can bound
$\mathcal{N}\left(\mathcal{Z},\varepsilon\right)$. Then using Lipschitzity of
the mappings $\mathcal{Z}\mapsto\phi\mathcal{Z}$ and $\hat{\zeta_{k}}$, this
translates to a bound on
$\mathcal{N}(\mathcal{F}_{k}(\mathcal{J}^{k}_{a,a^{\prime}}),\varepsilon)$.

We now consider the bounded amplification case Corollary: Given $a>0$, set

$\mathcal{G}^{k}_{a}=\left\\{A\hskip 5.69054pt|\hskip
5.69054ptA\in\mathbb{R}^{d\times k},\left\|A\right\|_{2,\infty}\leq
a\right\\}.$ (14)

######  Corollary 3.

Assume that $\left\|x_{i}\right\|\leq b$ for all $i\leq n$. Then for the set
$\mathcal{G}_{a}^{k}$ defined by (14) we have

$\mathfrak{R}\left(\mathcal{F}_{k}(\mathcal{G}^{k}_{a})\right)\leq\overline{O}\left(\frac{1}{n}+\frac{a^{2}b^{2}\sqrt{k}\left\|\phi\right\|^{2}_{Lip}}{\sqrt{n}}\right).$
(15)

The proof is given in Supplementary Material Section B.

###  5.2 Bounded Amplification Case

######  Theorem 4.

Assume that $\left\|x_{i}\right\|\leq b$ for all $i\leq n$. Then for the set
$\mathcal{G}_{a}^{k}$ defined by (14) we have

$\mathfrak{R}\left(\mathcal{F}_{k}(\mathcal{G}^{k}_{a})\right)\leq\overline{O}\left(1/n+\frac{a^{2}b^{2}\left\|\phi\right\|^{2}_{Lip}}{\sqrt{n}}\right).$
(16)

The proof of this result is given in Section C of the supplementary material.
We will now discuss a dimension reduction proof, which yields a somewhat
weaker, but still dimension independent bound:

$\mathfrak{R}\left(\mathcal{F}_{k}(\mathcal{G}^{k}_{a})\right)\leq\overline{O}\left(1/n+\frac{a^{2}b^{2}\left\|\phi\right\|^{2}_{Lip}}{n^{1/4}}\right).$
(17)

To make notation more compact, for any $l>0$ denote
$\mathcal{F}_{l}=\mathcal{F}_{l}(\mathcal{G}^{l}_{a})$. The main step of the
proof of (17), Lemma 5, is to show that every $f\in\mathcal{F}_{k}$ can be
approximated by $\hat{f}\in\mathcal{F}_{l}$ for any $l\leq k$, such that,
roughly, $\left\|f-\hat{f}\right\|_{\infty}\leq 1/\sqrt{l}$. This can be
equivalently restated as follows: The set $\mathcal{F}_{l}$, of
$l$-dimensional distance functions, approximates _any_ $\mathcal{F}_{k}$ up to
$1/\sqrt{l}$, independently of $k$. We refer to this property as _l-uniform
approximability_ , with rate $1/\sqrt{l}$.

######  Lemma 5.

For any $l\leq k$, for any $f\in\mathcal{F}_{k}$, there is
$\hat{f}\in\mathcal{F}_{l}$ such that

$\left\|f-\hat{f}\right\|_{\infty}\leq\frac{\left(ab\left\|\phi\right\|_{Lip}\right)^{2}\sqrt{\log
4n}}{\sqrt{l}}.$ (18)

###### Proof.

Fix $i\leq n$, and $A\in\mathcal{G}^{k}_{a}$. For $j\leq k$ set
$r_{j}=(\phi(A^{t}x_{i})_{j}-\phi(A^{t}x^{\prime}_{i})_{j})^{2}$ and denote
$r=(r_{1},\dots,r_{k})\in\mathbb{R}^{k}$. Set
$\bar{r}=\frac{1}{k}\sum_{j=1}^{k}r_{j}$. We have by definition that
$\zeta_{k}(\phi(A^{t}x_{i}),\phi(A^{t}x^{\prime}_{i}))=\bar{r}$. To obtain an
approximation in $\mathbb{R}^{l}$, we will choose $l$ coordinates $r_{j}$ at
random and consider the restriction to these coordinates.

For $l>0$ let $\pi:\mathbb{R}^{k}\rightarrow\mathbb{R}^{l}$ be a random
coordinate projection. That is, choose indices $i_{1},\ldots,i_{l}$
independently at random from $\left\\{1,\ldots,k\right\\}$ and set
$\pi(v)=\left(v_{i_{1}},\ldots,v_{i_{l}}\right)$ for all $v\in\mathbb{R}^{k}$.
Denote by $\hat{r}$ the empirical average $\hat{r}=\overline{\pi
r}=\frac{1}{l}\sum_{j=1}^{l}(\pi r)_{j}$.

Note that for every $j\leq k$, $\phi(\left<A_{\cdot j},x_{i}\right>)\leq
ab\left\|\phi\right\|_{Lip}$ and thus $\left\|r\right\|_{\infty}\leq
a^{2}b^{2}\left\|\phi\right\|_{Lip}^{2}$. Therefore by Bernstein’s inequality,
[Boucheron et al., 2013],

$\mathbb{P}_{\pi}\left(\left|\hat{r}-\bar{r}\right|>t\right)\leq
2exp\left(-l\cdot t^{2}/\left(ab\left\|\phi\right\|_{Lip}\right)^{4}\right).$
(19)

Finally, recall that $r$ depends on $i$. Repeating this for every $i\leq n$
and using the union bound,

$\mathbb{P}_{\pi}\left(\max_{i\leq n}\left|\hat{r}-\bar{r}\right|>t\right)\leq
2nexp\left(-l\cdot t^{2}/\left(ab\left\|\phi\right\|_{Lip}\right)^{4}\right).$
(20)

Choosing $t_{0}=\frac{\left(ab\left\|\phi\right\|_{Lip}\right)^{2}\sqrt{\log
4n}}{\sqrt{l}}$, the right handside of (20) is strictly smaller than 1.
Therefore there is a choice $\pi$ such that for all $i\leq n$,
$\left|\hat{r}-\bar{r}\right|\leq t_{0}$.

Finally, given $A\in\mathbb{R}^{d\times k}$ and $\pi=(i_{1},\ldots,i_{l})$,
denote by $A\pi\in\mathbb{R}^{d\times l}$ the restriction of A to $\pi$,
$A\pi=(A_{\cdot i_{1}},\ldots,A_{\cdot i_{l}})$. Note that if
$A\in\mathcal{G}_{a}^{k}$ then $A\pi\in\mathcal{G}_{a}^{l}$. If one denotes
$f_{A}(i)=\zeta_{k}(\phi(A^{t}x_{i}),\phi(A^{t}x^{\prime}_{i}))$, then we have
shown that for the particular $\pi$ found above $\max_{i\leq
n}\left|f_{A}(i)-f_{A\pi}(i)\right|\leq t_{0}$, thereby completing the proof.
∎

(a) Losses (b) $\left\|A\right\|_{2,\infty}$, $\left\|A\right\|_{2,1}/k$ and
$\left\|A\right\|_{op}/\sqrt{k}$ Weight Norms, Sigmoid Embedding. (c)
Same/Different Class Components of the Loss

Figure 2:  MNIST Experiment

To prove (17) from Lemma 5, it is suffices to note that for any $l<k$ one can
write
$\mathfrak{R}\left(\mathcal{F}_{k}(\mathcal{G}^{k}_{a})\right)\leq\mathfrak{R}\left(\mathcal{F}_{l}(\mathcal{G}^{l}_{a})\right)+\mathfrak{R}\left(\Delta\mathcal{F}_{k,l}\right)$
where $\Delta\mathcal{F}_{k,l}=\left\\{f-\hat{f}\hskip 5.69054pt|\hskip
5.69054ptf\in\mathcal{F}\right\\}$. The first term can be bounded by Corollary
3, the second by Lemma 5, and an appropriate choice of $l$ yields (17). The
full details are given in Supplementary Material Section D.

We conclude this Section with a brief discussion of the multi-layer networks
and of the role of the normalization by $k$ in (1).

######  Remark 6.

The special feature of metric learning compared to a regular classification
problem is the particular structure of the loss. That is, that the loss
depends on the features only through the metric $\rho$. In Theorem 1, however,
we have only exploited the Lipschitzity of $\rho$. We therefore note that it
is possible to obtain a multi-layer version of Theorem 1 simply by replacing
in our proof the single layer covering numbers bound (13) with a multi-layer
bound ([Bartlett et al., 2017], Theorem 3.3).

Moreover, since both our proofs of Theorem 4 eventually invoke Theorem 1 for
low $k$, it is clearly possible to also extend Theorem 4 to the multi-layer
case. In that case, the bound would depend on the $\left\|\cdot\right\|_{op}$
and $\left\|\cdot\right\|_{2,1}$ norms of all the layers except the last one,
in a way similar to Theorem 1.1, [Bartlett et al., 2017]. The dependence on
the last layer, however, would be only through
$\left\|\cdot\right\|_{2,\infty}$. In particular, we would still have
$\sqrt{k}$ factor improvement over Theorem 1. On the other hand, it seems
unlikely that the special properties of $\rho$ can be pushed further, to have
only $\left\|\cdot\right\|_{2,\infty}$ dependence also in lower layers.

######  Remark 7.

As noted earlier, the normalization by $k$ in (1) (or in the definition of
$\zeta_{k}$) is crucial to the fact that (5) is dimension free. However, this
is a natural normalization, ensuring that the values of $\rho_{k,f^{*}}$ are
of the same magnitude ( $0\leq\rho_{k,f^{*}}\leq
4\left\|A\right\|_{2,\infty}^{2}b^{2}$) independently of $k$, rather than
explode with $k$. Note that if one normalized by anything of larger order than
$k$, then the situation would have been degenerate, since $\rho_{k,f^{*}}$
values would simply be vanishing as $k$ grows. However, with normalization by
$k$ this is not the case. The values of $\rho_{k,f^{*}}$ stay bounded but non-
vanishing, while the number of parameters grows with $k$. Equivalently, while
the magnitude of the values of $\rho_{k,f^{*}}$ stays bounded, the family of
functions $\mathcal{F}_{k}(\mathcal{G}^{k}_{a})$ becomes strictly larger as
$k$ grows. Thus the fact that the Rademacher complexity (5) is bounded
independently of $k$ is non-trivial.

##  6 Experiments

In this Section we empirically make the following observations: (a) The
bounded amplification regime introduced in this paper, where
$\left\|A\right\|_{2,\infty}$ is bounded while $\left\|A\right\|_{2,1}$ and
$\left\|A\right\|_{op}$ grow with $k$, occurs naturally in practice. For
instance, we observe this on the MNIST data, trained without any
regularization terms. (b) The generalization gap, i.e. the difference between
train and test loss, does not grow with $k$, for $k$ in the range from 1 to
5000, as suggested by the theory. In other words, we can increase $k$
arbitrarily, without risking overfitting. (c) The non-linear embeddings, even
with a single layer, can perform better than the linear ones. Note that this
point is not necessarily completely obvious. The linear embeddings are fairly
powerful, and can, for instance, do things such as removing coordinates that
are irrelevant to the label, thereby improving the relation between the metric
and the label. Nevertheless, we find that on both our datasets, a sigmoid non-
linearity improves the performance of the embedding.

We consider two classical datasets, the MNIST dataset of handrwitten digits
[mnist Dataset,], and the 20newsgroups dataset [20newsgoups Dataset,], which
consists of newsgroups emails, labeled according to the group. To make
illustrations simpler, we restrict the 20newsgroups to the first 10 labels.
While MNIST is generally nicely behaved, the 20newgroups is not. In
particular, it consists of about $n=7500$ samples in dimension $d=15000>n$,
and this would require explicitly regularizing $\left\|A\right\|_{2,\infty}$.
In all cases, we consider a single layer fully connected embedding, as in (3),
where the activation function $\phi$ is either $\phi(x)=x$ (linear case) or
$\phi(x)=\sigma(x)=\frac{1}{1+e^{-x}}$.

(a) Losses (b) $\left\|A\right\|_{2,\infty}$, $\left\|A\right\|_{2,1}/k$ and
$\left\|A\right\|_{op}/\sqrt{k}$ Weight Norms, Sigmoid Embedding. (c)
Same/Different Class Components of the Loss

Figure 3:  Newsgroups Experiment

To perform the optimization, we sample feature/label pairs $(x,l)$,
$(x^{\prime},l^{\prime})$ independently from the train set, and minimize the
loss using SGD on batches of such pairs, until convergence. The loss that we
use is

$\displaystyle\ell(x,x^{\prime},l,l^{\prime})=$ $\displaystyle 9\cdot
ReLU(\rho(x,x^{\prime}))\cdot\mathbbm{1}_{\left\\{l=l^{\prime}\right\\}}$
$\displaystyle+ReLU(D-\rho(x,x^{\prime}))\cdot\mathbbm{1}_{\left\\{l\neq
l^{\prime}\right\\}},$ (21)

where $\rho(x,x^{\prime})$ is the distance after the embedding, given by (1).
This loss is a version of the loss $\ell_{S,D}^{\lambda}(\rho,y)$ introduced
in Section 2, where the same class case is weighted by 9. Our datasets have 10
roughly balanced labels, and therefore the probability of the event
$l=l^{\prime}$ is about $1/10$. Thus the multiplier 9 helps in giving similar
weights to the separation $l\neq l^{\prime}$ and the compression
$l=l^{\prime}$ conditions, enforced by the respective terms in (21). For train
or test evaluation, we sample the pairs $(x,l)$, $(x^{\prime},l^{\prime})$
from the train or test set, respectively, and compute the mean value of
$\ell(x,x^{\prime},l,l^{\prime})$ on these samples. For MNIST we use the upper
threshold $D=0.5$, while for 20newsgroups we set $D=0.1$.

Each experiment was repeated 6 times, and every value in Figures 2, 3 is a
mean over 6 outcome values. Every value also has an error bar which indicates
the magnitude of the standard deviation around the mean. However, in most
cases, these bars are so small compared to the magnitude of the mean, that
they are not visible in the figures. Additional details on the experimental
setting are given in Supplementary Material Section E. The full code that was
used for the experiments is also provided as Supplementary Material. We now
discuss each dataset separately.

###  6.1 MNIST

For MNIST, the feature dimension is $d=28\cdot 28=784$. As mentioned earlier,
in this experiment we do not use any regularization terms on the embedding
weight matrix $A$. The results are shown in Figure 2. First, Figure 2(b) shows
the norms of $A$ after the convergence of the optimization, for the sigmoid
embeddings. The $\left\|A\right\|_{2,\infty}$ is given by the green solid
line, for values of $k$ ranging from 1 to 5000. The values of
$\left\|A\right\|_{2,1}/k$ and $\left\|A\right\|_{op}/\sqrt{k}$ are given by
the dashed red and purple lines, respectively. The fact that all three lines
remain of the same magnitude throughout the whole range of $k$ means that the
standard non reguilarized SGD optimization works in this case in the bounded
amplification regime. That is, the $\left\|A\right\|_{2,\infty}$ norm remains
roughly bounded while $\left\|A\right\|_{2,1}$ grows linearly with $k$ and
$\left\|A\right\|_{op}$ grows linearly with $\sqrt{k}$. The situation for the
linear case is similar (see Figure 4(a) in the Supplementary Material).

Next, we consider the losses on train and test sets, Figure 2(a). For the
sigmoid embedding, the blue solid line is the loss evaluated on the train set,
while the blue dashed line is the test loss. Observe that the lines are
practically identical as $k$ grows. There is no deterioration of the
generalization gap as $k$ grows. This may appear somewhat counterintuitive at
first. However, according to Figure 2(b), we are in the non-sparse, bounded
$\left\|A\right\|_{2,\infty}$ norm regime. Therefore our results, in
particular Theorem 4, suggest that indeed the generalization gap should be
independent of $k$. Similar picture occurs for the linear case, as shown by
the orange lines. Note that the non-linear loss is considerably lower than the
linear one.

Finally, since the loss expression (21) is rather involved, it may be unclear
from the raw values of the loss whether there is actually any good separation
of the labels in the learned metric. In Figure 2(c) we show explicitly the
same class and different class components of the loss. That is, for the
sigmoid embedding, the solid blue line in Figure 2(c) is the average of the
quantity $ReLU(\rho(x,x^{\prime}))$ over pairs of features $(x,x^{\prime})$ on
_test set_ for which $l=l^{\prime}$ (that is, conditioned on the fact that
labels are equal), while the dashed blue line is the average of
$ReLU(0.5-\rho(x,x^{\prime}))$ on pairs with $l\neq l^{\prime}$. Thus for
instance, for $k=10$, at least on average, points with the same label are at
distance $0.07$ while points with different labels are at distance
$0.5-0.12=0.38$.

###  6.2 Newsgroups

As mentioned earlier, the 20newsgrous dataset [20newsgoups Dataset,] was
restricted to the first 10 labels. Each email was represented as a bag-of-
words vector over $d=15000$ most common tokens in the dataset. Each vector was
then normalized to have Euclidean norm 1. This dataset contains 9640 samples,
of which $20\%$ were taken at random as the test set, leaving $n=7700$ train
samples. Since $d>n$, one can in principle severely overfit the data even with
$k=1$. Thus one has to control the $\left\|A\right\|_{2,\infty}$ norm, which
was achieved by adding the term $\frac{0.1}{d}\left\|A\right\|^{2}_{2,\infty}$
to the loss (21) in the sigmoid case, and
$\frac{1.0}{d}\left\|A\right\|^{2}_{2,\infty}$ in the linear case. The
regularization values $0.1$ and $1.0$ above where chosen such as to yield the
best test performance at $k=10$ in their respective cases.

The experiment results are shown in Figure 3, with plots similar to those of
the MNIST dataset. In particular, we see in Figure 3(b) that while we enforce
the bounded $\left\|A\right\|_{2,\infty}$ norm constraint with the
regularization term, there was no sparsity, i.e. $\left\|A\right\|_{2,1}$ and
$\left\|A\right\|_{op}$ grew with $k$, as in the MNIST case. The
generalization gap, Figure 3(a) was considerable, but it was _the same gap_
throughout the larger values of $k$ ($k\geq 5$). This can also be seen in
Figure 3(c) – the values of the same class/different class expectations on the
test set remain relatively constant over the range of $k$. Recall that the
test set for $k=50$ was shown in Figure 1(b), and corresponds to fairly good
label separation, as can be expected from the values in Figure 3(c).

##  7 Conclusion

In this work we have provided the first uniform generalization guarantees for
metric learning with a non-linear embedding. In particular, we have shown that
dimension free generalization is possible in the non-sparse regime.

We believe that further study of the non sparse regime, and in particular
understanding better in which other situations the non sparse regime occurs,
and what are the associated bounds, would significantly advance our
understanding overparametrized systems. In addition, observe that almost _any_
family of sets $\mathcal{U}_{l}\subset\mathbb{R}^{n}$ , $l\geq 1$, (given,
say, trivial compactness constraints) has the $l$-approximability property, as
introduced in Section 5.2, for _some_ , necessarily vanishing, rate. We
believe that the study of machine learning problems through the lens of such
rates of their induced restrictions $\mathcal{U}_{l}$ is a very promising new
research direction.

## References

  * [20newsgoups Dataset, ] 20newsgoups Dataset.  20newsgoups dataset.  https://scikit-learn.org/stable/datasets/real_world.html#newsgroups-dataset.
  * [Bartlett, 1998] Bartlett, P. (1998).  The sample complexity of pattern classification with neural networks: the size of the weights is more important than the size of the network.  IEEE Transactions on Information Theory, 44.
  * [Bartlett et al., 2017] Bartlett, P. L., Foster, D. J., and Telgarsky, M. J. (2017).  Spectrally-normalized margin bounds for neural networks.  In Advances in Neural Information Processing Systems, pages 6240–6249.
  * [Bartlett and Mendelson, 2002] Bartlett, P. L. and Mendelson, S. (2002).  Rademacher and gaussian complexities: Risk bounds and structural results.  J. Mach. Learn. Res., 3.
  * [Bellet and Habrard, 2015] Bellet, A. and Habrard, A. (2015).  Robustness and generalization for metric learning.  Neurocomputing, 151:259–267.
  * [Bellet et al., 2015] Bellet, A., Habrard, A., and Sebban, M. (2015).  Metric learning.  Synthesis Lectures on Artificial Intelligence and Machine Learning, 9(1):1–151.
  * [Boucheron et al., 2013] Boucheron, S., Lugosi, G., and Massart, P. (2013).  Concentration inequalities: a nonasymptotic theory of independence.  Oxford University Press, Oxford, 1st ed edition.
  * [Bousquet and Elisseeff, 2002] Bousquet, O. and Elisseeff, A. (2002).  Stability and generalization.  J. Mach. Learn. Res.
  * [Bousquet et al., 2020] Bousquet, O., Klochkov, Y., and Zhivotovskiy, N. (2020).  Sharper bounds for uniformly stable algorithms.  In Conference on Learning Theory, pages 610–626. PMLR.
  * [Cao et al., 2016] Cao, Q., Guo, Z.-C., and Ying, Y. (2016).  Generalization bounds for metric and similarity learning.  Machine Learning, 102(1):115–132.
  * [Chicco, 2020] Chicco, D. (2020).  Siamese neural networks: An overview.  Artificial Neural Networks, pages 73–94.
  * [Christmann and Zhou, 2016] Christmann, A. and Zhou, D.-X. (2016).  On the robustness of regularized pairwise learning methods based on kernels.  Journal of Complexity, 37:1–33.
  * [Davis et al., 2007] Davis, J. V., Kulis, B., Jain, P., Sra, S., and Dhillon, I. S. (2007).  Information-theoretic metric learning.  In Proceedings of the 24th international conference on Machine learning, pages 209–216.
  * [Feldman and Vondrak, 2019] Feldman, V. and Vondrak, J. (2019).  High probability generalization bounds for uniformly stable algorithms with nearly optimal rate.  COLT.
  * [Hastie et al., 2015] Hastie, T., Tibshirani, R., and Wainwright, M. (2015).  Statistical learning with sparsity: the lasso and generalizations.  CRC press.
  * [Khosla et al., 2020] Khosla, P., Teterwak, P., Wang, C., Sarna, A., Tian, Y., Isola, P., Maschinot, A., Liu, C., and Krishnan, D. (2020).  Supervised contrastive learning.  arXiv preprint arXiv:2004.11362.
  * [Lei et al., 2020] Lei, Y., Ledent, A., and Kloft, M. (2020).  Sharper Generalization Bounds for Pairwise Learning.  In Advances in Neural Information Processing Systems.
  * [Maaten and Hinton, 2008] Maaten, L. v. d. and Hinton, G. (2008).  Visualizing data using t-sne.  Journal of machine learning research.
  * [mnist Dataset, ] mnist Dataset.  Mnist dataset.  https://keras.io/api/datasets/mnist/.
  * [Mohri et al., 2018] Mohri, M., Rostamizadeh, A., and Talwalkar, A. (2018).  Foundations of machine learning.  The MIT Press, second edition edition.
  * [Schapire et al., 1998] Schapire, R. E., Freund, Y., Bartlett, P., and Lee, W. S. (1998).  Boosting the margin: a new explanation for the effectiveness of voting methods.  The Annals of Statistics, 26.
  * [Schroff et al., 2015] Schroff, F., Kalenichenko, D., and Philbin, J. (2015).  Facenet: A unified embedding for face recognition and clustering.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 815–823.
  * [Verma and Branson, 2015] Verma, N. and Branson, K. (2015).  Sample complexity of learning mahalanobis distance metrics.  In Cortes, C., Lawrence, N., Lee, D., Sugiyama, M., and Garnett, R., editors, Advances in Neural Information Processing Systems, volume 28.
  * [Vershynin, 2018] Vershynin, R. (2018).  High-Dimensional Probability: An Introduction with Applications in Data Science.  Cambridge University Press, 1 edition.
  * [Wang et al., 2019] Wang, B., Zhang, H., Liu, P., Shen, Z., and Pineau, J. (2019).  Multitask metric learning: Theory and algorithm.  In Proceedings of Machine Learning Research, volume 89 of Proceedings of Machine Learning Research. PMLR.
  * [Weinberger and Saul, 2009] Weinberger, K. Q. and Saul, L. K. (2009).  Distance metric learning for large margin nearest neighbor classification.  J. Mach. Learn. Res., 10.
  * [Xu and Mannor, 2012] Xu, H. and Mannor, S. (2012).  Robustness and generalization.  Machine learning, 86(3):391–423.
  * [Zhang, 2002] Zhang, T. (2002).  Covering number bounds of certain regularized linear function classes.  Journal of Machine Learning Research, 2(Mar):527–550.
  * [Zhou et al., 2019] Zhou, W., Veitch, V., Austern, M., Adams, R. P., and Orbanz, P. (2019).  Non-vacuous generalization bounds at the imagenet scale: a pac-bayesian compression approach.  In International Conference on Learning Representations.

Dimension Free Generalization Bounds for Non Linear Metric Learning

Supplementary Material

##  Appendix A Proof of Theorem 1

We will require the following bound on the Lipschitz constant of $\zeta_{k}$.

######  Lemma 8.

For $x,x^{\prime},y,y^{\prime}\in\mathbb{R}^{k}$ set
$\gamma=\max\left\\{\left\|x\right\|_{2},\left\|x^{\prime}\right\|_{2},\left\|y\right\|_{2},\left\|y^{\prime}\right\|_{2}\right\\}$.
Then

$\left|\zeta_{k}(x,x^{\prime})-\zeta_{k}(y,y^{\prime})\right|\leq\frac{8\gamma}{k}\left(\left\|x-y\right\|_{2}+\left\|x^{\prime}-y^{\prime}\right\|_{2}\right).$
(22)

###### Proof.

Set $\Delta=x-y,\Delta^{\prime}=x^{\prime}-y^{\prime}$. Clearly
$\left\|x-x^{\prime}\right\|_{2}\leq 2\gamma$, and
$\left\|\Delta-\Delta^{\prime}\right\|_{2}\leq 4\gamma$. We have

$\displaystyle\left|\zeta_{k}(x,x^{\prime})-\zeta_{k}(y,y^{\prime})\right|$
$\displaystyle=\frac{1}{k}\left|\left\|x-x^{\prime}\right\|_{2}^{2}-\left\|x-x^{\prime}-\Delta+\Delta^{\prime}\right\|_{2}^{2}\right|$
$\displaystyle=\frac{1}{k}\left|-2\left<x-x^{\prime},\Delta-\Delta^{\prime}\right>-\left\|\Delta-\Delta^{\prime}\right\|_{2}^{2}\right|$
$\displaystyle=\frac{1}{k}\left|-2\left<x-x^{\prime},\Delta-\Delta^{\prime}\right>-\left<\Delta-\Delta^{\prime},\Delta-\Delta^{\prime}\right>\right|$
$\displaystyle\leq\frac{1}{k}\left(4\gamma\left(\left\|\Delta\right\|_{2}+\left\|\Delta^{\prime}\right\|_{2}\right)+4\gamma\left(\left\|\Delta\right\|_{2}+\left\|\Delta^{\prime}\right\|_{2}\right)\right).$

∎

###### Proof of Theorem 1.

Denote throughout of the proof
$\mathcal{F}:=\mathcal{F}_{k}(\mathcal{J}^{k}_{a,a^{\prime}})$. Our plan is to
bound the covering numbers $\log\mathcal{N}(\mathcal{F},\varepsilon)$ and then
to use the Dudley entropy bound for the Rademacher complexity. Fix
$\varepsilon>0$. Let $\mathcal{M}$ and $\mathcal{M}^{\prime}$ be
$\varepsilon$-covers for the sets $X\mathcal{J}_{a}^{k}$ and
$X^{\prime}\mathcal{J}_{a}^{k}$, such that $\log\left|\mathcal{M}\right|$ and
$\log\left|\mathcal{M}^{\prime}\right|$ are at most
$\frac{a^{2}b^{2}n}{\varepsilon^{2}}\log(2dk)$, as guaranteed by Lemma 2. Then
the set $\mathcal{M}\times\mathcal{M}^{\prime}$ is an
$\sqrt{2}\varepsilon$-cover for the set
$\mathcal{Z}=\left\\{(XA,X^{\prime}A)\hskip 5.69054pt|\hskip
5.69054ptA\in\mathcal{J}_{a,a^{\prime}}^{k}\right\\}\subset\mathbb{R}^{n\times
2k}$. Note that the elements of $\mathcal{M}\times\mathcal{M}^{\prime}$ are
not necessarily members of $\mathcal{Z}$. However, by taking projections onto
$\mathcal{Z}$, we can find an $2\sqrt{2}\varepsilon$-cover of size at most
$\left|\mathcal{M}\right|\times\left|\mathcal{M}^{\prime}\right|$ with
elements inside $\mathcal{Z}$. Denote such a cover by $\mathcal{P}$.

Let $\phi\mathcal{Z}$ denote the image of $\mathcal{Z}$ under $\phi$, acting
coordinatewise, and denote by $\hat{\zeta_{k}}:\mathbb{R}^{n\times
2k}\rightarrow\mathbb{R}^{n}$ the map that applies $\zeta_{k}$ on the rows. In
particular, for every $A$ and every coordinate $i\leq n$, we have

$\hat{\zeta_{k}}\left(\phi\left(\left(XA,X^{\prime}A\right)\right)\right)_{i}=\zeta_{k}\left(\phi(A^{t}x_{i}),\phi(A^{t}x^{\prime}_{i})\right).$
(23)

Equivalently, by definition, we have that
$\mathcal{F}=\hat{\zeta_{k}}\left(\phi\left(\mathcal{Z}\right)\right)$.

Finally, since $\phi(0)=0$, for any $x_{i}$ and
$A\in\mathcal{J}_{a,a^{\prime}}^{k}$ we have

$\left\|\phi(A^{t}x_{i})\right\|_{2}\leq
ba^{\prime}\left\|\phi\right\|_{Lip}.$ (24)

It therefore follows by Lemma 8 that $\hat{\zeta_{k}}$ is
$\frac{\sqrt{2}8ba^{\prime}\left\|\phi\right\|_{Lip}}{k}$-Lipschitz as a
function from $\phi(\mathcal{Z})$ to $\mathbb{R}^{n}$. Consequently, a
$2\sqrt{2}\varepsilon$-cover $\mathcal{P}$ of $\mathcal{Z}$ is mapped by
$\hat{\zeta_{k}}\circ\phi$ into an
$2\sqrt{2}\cdot\frac{\sqrt{2}8ba^{\prime}\left\|\phi\right\|_{Lip}}{k}\cdot\left\|\phi\right\|_{Lip}\cdot\varepsilon$-cover
of $\mathcal{F}$.

Combining the above statements, we have shown that there is an absolute
constant $c>0$ such that for any $\varepsilon>0$,

$\log\mathcal{N}(\mathcal{F},\varepsilon)\leq c\frac{a^{2}a^{\prime
2}b^{4}n\left\|\phi\right\|_{Lip}^{4}}{k^{2}\varepsilon^{2}}\log(2dk).$ (25)

Set $D=diam(\mathcal{F})=\sup_{u,v\in\mathcal{F}}\left\|u-v\right\|_{2}$.
Using (24) again, we have $D\leq\frac{4b^{2}a^{\prime
2}\left\|\phi\right\|_{Lip}^{2}}{k}\cdot\sqrt{n}$. Next, by Dudley’s entropy
bound, [Vershynin, 2018], and using (25), for any $\delta>0$,

$\displaystyle\mathfrak{R}\left(\mathcal{F}\right)$
$\displaystyle\leq\frac{4\delta}{\sqrt{n}}+\frac{12}{n}\int_{\delta}^{D/2}\sqrt{\log\mathcal{N}(\mathcal{F},\varepsilon)}d\varepsilon$
$\displaystyle\leq\frac{4\delta}{\sqrt{n}}+\frac{12\sqrt{c}}{\sqrt{n}}\frac{aa^{\prime}b^{2}\left\|\phi\right\|^{2}_{Lip}}{k}\log\left(D/\delta\right).$

Taking $\delta=\frac{1}{\sqrt{n}}$ and using the above bound on $D$ completes
the proof. ∎

##  Appendix B Proof of Corollary 3

###### Proof.

For any $A\in\mathbb{R}^{d\times k}$, we have $\left\|A\right\|_{2,1}\leq
k\left\|A\right\|_{2,\infty}$ and
$\left\|A\right\|_{op}\leq\sqrt{k}\left\|A\right\|_{2,\infty}$. The first
inequality follows immediately from the definitions. For the second inequality
observe that

$\displaystyle\left\|A\right\|_{op}=\left\|A^{t}\right\|_{op}$
$\displaystyle=\sup_{\left\|v\right\|_{2}=1}\left\|A^{t}v\right\|=\sup_{\left\|v\right\|_{2}=1}\left(\sum_{i=1}^{k}\left<A_{\cdot
i},v\right>^{2}\right)^{\frac{1}{2}}$ $\displaystyle\leq\left(k\max_{i\leq
k}\left\|A_{\cdot
i}\right\|_{2}^{2}\right)^{\frac{1}{2}}=\sqrt{k}\left\|A\right\|_{2,\infty}.$

The two inequalities above imply that
$\mathcal{G}_{a}^{k}\subset\mathcal{J}_{ka,\sqrt{k}a}^{k}$ and thus the
Corollary follows from Theorem 1. ∎

##  Appendix C First Proof of Theorem 4

###### Proof 1 of Theorem 4:.

For any set of families of functions $\mathcal{H}_{i}$, $i\leq m$, define the
sum $\oplus_{i=1}^{m}\mathcal{H}_{i}$ by
$\oplus_{i=1}^{m}\mathcal{H}_{i}=\left\\{g=\sum_{i=1}^{m}h_{i}\hskip
5.69054pt|\hskip 5.69054pth_{i}\in\mathcal{H}_{i}\right\\}$. For a scalar
$\alpha$ set also $\alpha\mathcal{H}=\left\\{\alpha h\hskip 5.69054pt|\hskip
5.69054pth\in\mathcal{H}\right\\}$. We observe the following:

$\mathcal{F}_{k}(\mathcal{G}^{k}_{a})=\frac{1}{k}\left(\oplus_{i=1}^{k}\mathcal{F}_{1}(\mathcal{G}^{1}_{a})\right),$
(26)

where the expression on the right handside is the sum of
$\mathcal{F}_{1}(\mathcal{G}^{1}_{a})$ taken $k$ times, normalized by
$\frac{1}{k}$. This equality is a consequence of the definition of $\zeta_{k}$
as an average, and of the fact that $\mathcal{G}^{k}_{a}$ is a product set of
its individual columns. More explicitly, given $A\in\mathcal{G}_{a}^{k}$, the
vector in $\mathcal{F}_{k}(\mathcal{G}^{k}_{a})$ corresponding to $A$ is, by
definition,
$\left(\zeta_{k}(\phi(A^{t}x_{i}),\phi(A^{t}x^{\prime}_{i})\right)_{i=1}^{n}\in\mathbb{R}^{n}$.
For a fixed coordinate $i\leq n$ we have

$\displaystyle\zeta_{k}(\phi(A^{t}x_{i}),\phi(A^{t}x^{\prime}_{i}))$
$\displaystyle=\frac{1}{k}\sum_{j=1}^{k}\left(\phi((A^{t}x_{i})_{j})-\phi((A^{t}x^{\prime}_{i})_{j})\right)^{2}$
$\displaystyle=\frac{1}{k}\sum_{j=1}^{k}\left(\phi(A_{\cdot
j}^{t}x_{i})-\phi(A_{\cdot j}^{t}x^{\prime}_{i})\right)^{2},$ (27)

where $(A^{t}x_{i})_{j}$ is the $j$-th coordinate of $(A^{t}x_{i})$ and
$A_{\cdot j}^{t}x_{i}$ is the product of $A$ restricted to its $j$-th column
with $x_{i}$. Since each term in the sum (27) is in $\mathcal{G}_{a}^{1}$, the
claim (26) follows.

Next, one can readily verify that for any set of families $\mathcal{H}_{i}$,
we have
$\mathfrak{R}\left(\oplus_{m}\mathcal{H}_{m}\right)=\sum_{i=1}^{m}\mathfrak{R}\left(\mathcal{H}_{i}\right)$,
and
$\mathfrak{R}\left(\alpha\mathcal{H}\right)=\alpha\mathfrak{R}\left(\mathcal{H}\right)$
for $\alpha\geq 0$ (see [Bartlett and Mendelson, 2002], [Mohri et al., 2018]
). Therefore, using (26) we have

$\mathfrak{R}\left(\mathcal{F}_{k}(\mathcal{G}^{k}_{a})\right)=\mathfrak{R}\left(\mathcal{F}_{1}(\mathcal{G}^{1}_{a})\right).$
(28)

The statement now follows from Corollary 3 applied with $k=1$. ∎

##  Appendix D Second Proof of Theorem 4

###### Proof 2 of Theorem 4, Dimension Reduction:.

Fix $l<k$, and set
$t_{0}=\frac{\left(ab\left\|\phi\right\|_{Lip}\right)^{2}\sqrt{\log
4n}}{\sqrt{l}}$. By Lemma 5, for every $f\in\mathcal{F}_{k}$ one can write
$f=\hat{f}+(f-\hat{f})$ such that $\hat{f}\in\mathcal{F}_{l}$ and
$\left\|f-\hat{f}\right\|_{\infty}\leq t_{0}$. It follows that

$\displaystyle\mathfrak{R}\left(\mathcal{F}_{k}\right)=\frac{1}{n}\mathbb{E}_{\varepsilon}sup_{f\in\mathcal{F}_{k}}\sum_{i=1}^{n}\varepsilon_{i}f_{i}$
$\displaystyle\leq\frac{1}{n}\mathbb{E}_{\varepsilon}sup_{f\in\mathcal{F}_{l}}\sum_{i=1}^{n}\varepsilon_{i}f_{i}+\frac{1}{n}\mathbb{E}_{\varepsilon}sup_{\left\|f\right\|_{\infty}\leq
t_{0}}\sum_{i=1}^{n}\varepsilon_{i}f_{i}$
$\displaystyle\leq\mathfrak{R}\left(\mathcal{F}_{l}\right)+t_{0}$
$\displaystyle\leq\left(\frac{1}{n}+c\cdot\frac{a^{2}b^{2}\sqrt{l}\left\|\phi\right\|^{2}_{Lip}}{\sqrt{n}}\log\left(na^{2}\sqrt{l}\left\|\phi\right\|_{Lip}\right)\right)$
$\displaystyle\hskip 5.69054pt\hskip 5.69054pt\hskip
5.69054pt+\frac{\left(ab\left\|\phi\right\|_{Lip}\right)^{2}\sqrt{\log
4n}}{\sqrt{l}},$

where the last inequality follows by Corollary 3. Minimizing the above
expression in $l$ yields (17). ∎

##  Appendix E Additional Details on Experiments

(a) MNIST Experiment. $\left\|A\right\|_{2,\infty}$,
$\left\|A\right\|_{2,1}/k$ and $\left\|A\right\|_{op}/\sqrt{k}$ Weight Norms,
Linear Embedding. (b) Newsgroups Experiment. $\left\|A\right\|_{2,\infty}$,
$\left\|A\right\|_{2,1}/k$ and $\left\|A\right\|_{op}/\sqrt{k}$ Weight Norms,
Linear Embedding.

  * •

The full code of the experiments is provided as a Supplementary Material. The
code is based on the Tensorflow framework. Details on the invocation can be
found in the README.md file.

  * •

The precise process of sampling the pairs $(x,x^{\prime})$ was as follows: We
fix two batch sizes $Bx,By$, typically $Bx=By=500$. We take a batch $S_{1}$ of
size $Bx$ and another, independent batch, $S_{2}$, of size $B_{y}$. Then the
set $S$ of all feature pairs $(x,x^{\prime})$ such that $x\in S_{1}$ and
$x^{\prime}\in S_{2}$ is created, with corresponding labels $y$ as described
in Section 1. This $S$ is fed to the optimizer as a single batch.

  * •

An _epoch_ is when first batch iterator, $S_{1}$, finishes a single iteration
over the whole data. The data is permuted at the end of the epoch.

  * •

All experiments were run for 180 epochs. Convergence typically occurred much
earlier, around 30 to 50 epochs, depending on the value of $k$.

  * •

All experiments were run on a GTX 1080 GPU, with Tensorflow 2.0. A single run
of the longest experiment, MNIST with $k=5000$, took under 150 minutes to
complete. All experiments combined, with repetitions, finish running in under
48 hours.


# Broadband Fiber-based Entangled Photon-Pair Source at Telecom O-band

Changjia Chen  Dept. of Electrical and Computer Engineering, University of
Toronto, 10 King’s College Rd., Toronto, M5S 3G4, Canada  Corresponding
author<EMAIL_ADDRESS>Calvin Xu  Dept. of Electrical and
Computer Engineering, University of Toronto, 10 King’s College Rd., Toronto,
M5S 3G4, Canada  Arash Riazi  Dept. of Electrical and Computer Engineering,
University of Toronto, 10 King’s College Rd., Toronto, M5S 3G4, Canada  Eric
Y. Zhu  Dept. of Electrical and Computer Engineering, University of Toronto,
10 King’s College Rd., Toronto, M5S 3G4, Canada  Alexey V.Gladyshev  Prokhorov
General Physics Institute of the Russian Academy of Sciences, Dianov Fiber
Optics Research Center, 38 Vavilov Street, 119333 Moscow, Russia  Peter G.
Kazansky  Optoelectronics Research Centre, University of Southampton,
Southampton SO17 1BJ, United Kingdom  Li Qian  Dept. of Electrical and
Computer Engineering, University of Toronto, 10 King’s College Rd., Toronto,
M5S 3G4, Canada

###### Abstract

In this letter, we report a polarization-entangled photon-pair source based on
type-II spontaneous parametric down conversion at telecom O-band in
periodically poled silica fiber (PPSF). The photon-pair source exhibits more
than 130 nm ($\sim$24 THz) emission bandwidth centered at 1306.6 nm. The broad
emission spectrum results in a short biphoton correlation time and we
experimentally demonstrate a Hong-Ou-Mandel interference dip with a full width
of 26.6 fs at half maximum. Owing to the low birefringence of the PPSF, the
biphotons generated from type-II SPDC are polarization-entangled over the
entire emission bandwidth, with a measured fidelity to a maximally entangled
state greater than 95.4$\%$. The biphoton source provides the broadest
bandwidth entangled biphotons at O-band to our knowledge.

††journal: ol

In the last few decades, the development of photon-pair sources has laid the
foundation for quantum photonic technologies. One of the most convenient
methods of producing entangled photon pairs is spontaneous parametric
downconversion (SPDC) in a second-order nonlinear medium. SPDC has been
extensively studied for its applications in quantum information processing and
photonic quantum computation[1]. By engineering the nonlinear medium, the
photon pairs generated by SPDC can be naturally endowed with nonclassical
correlations, such as entanglement in polarization[2] or in orbital angular
momentum[3] degrees of freedom. The frequency-time correlated biphotons in
SPDC sources are also of broad interest, as they enable quantum interferometry
that surpasses the limits of classical sensitivity[4].

In particular, broad bandwidth and time-correlated photon pairs are desirable
as they enable the investigation of the optical properties of a sample over a
wide spectral range, enhancing the spatial and temporal resolution of quantum
sensing[5]. Broadband photon-pair sources are also significant for quantum
communication techniques, such as wavelength-multiplexed entanglement
distribution[6] and clock synchronization[7]. For example, it is crucial to
use broadband time-correlated photon pairs for distant clock synchronization,
as its precision is limited by the biphoton correlation time[7]. However, in
fiber-based quantum communication where the biphotons are transmitted through
long-distance fiber links, precise dispersion compensation is needed because
the fiber’s chromatic dispersion will obscure the timing correlation. A
biphoton source centered near the zero-dispersion wavelength (around 1310 nm)
of the telecom silica fiber may resolve this problem and improve the precision
of timing[8]. Various entangled photon sources at telecom O-band (1260 - 1360
nm) with a biphoton emission bandwidth up to 70 nm have been developed[9, 10,
11, 12, 13, 14, 15, 16]. However, this bandwidth is still lacking. Generating
broadband and highly time-correlated photon pairs via the process of SPDC
remains a challenge. In order to use SPDC to generate broadband, time-
correlated biphotons, various methods have been employed, such as using a
short nonlinear medium[6] and chirped quasi-phase-matching[17], though at the
expense of reduced biphoton generation rates and complex fabrication
requirements. A time-correlated photon-pair source at O-band which has broader
bandwidth and is compatible with telecom fibers is still highly desired.

In addition to the time-frequency degree of freedom, the polarization
correlation within the biphotons generated via SPDC also attracts much
interest. Broadband biphotons with polarization entanglement can be used for
polarization sensitive quantum sensing[18] and multi-user quantum
communication[19]. However generating polarization entangled photons over a
broad bandwidth often requires stable compensation for the wavelength-
dependent birefringence of the nonlinear medium[6, 10]. Interferometric
methods or compensating components are therefore needed to achieve a high
polarization entanglement quality[20], increasing the experimental
difficulties.

A promising solution is to use a nonlinear medium of sufficient interaction
length but low birefringence and low chromatic dispersion to generate
broadband entangled photon pairs . In this letter, we demonstrate a cw-pumped
periodically poled silica fiber (PPSF) based entangled photon-pair source
quasi-phase-matched (QPM) at 1306.6 nm, which is near the zero-dispersion
wavelength of telecom single-mode silica fiber (e.g. SMF-28). The low
chromatic dispersion and the low birefringence of the PPSF at telecom O-band
result in a biphoton emission bandwidth greater than 130 nm ($>$ 24 THz in
frequency), which to our knowledge is the broadest bandwidth of polarization-
entangled biphotons at O-band. We demonstrate Hong-Ou-Mandel interference with
the biphoton source and measure an interference dip width of 26.6 $\pm$ 1.3
fs. We also perform quantum state tomography to measure the quality of
polarization entanglement. The concurrence[21] of the polarization
entanglement is measured to be more than 0.91 and the fidelity to a maximally
entangled state is measured to be more than 95.4$\%$. This broadband PPSF
source employs mature telecommunication components and eliminates beam
alignment. It is compatible with the existing low-loss telecom fiber links and
facilitates long-distance entanglement distribution and compensation-free
quantum clock synchronization.

To see how birefringence and chromatic dispersion affect the SPDC spectrum, we
may write the spectral brightness of an SPDC source as[22]:

$\displaystyle
I(\omega_{s},\omega_{i})\propto\mathrm{sinc}^{2}\left[\frac{L}{2}\left(k_{A}(\omega_{p})-k_{B}(\omega_{s})-k_{C}(\omega_{i})-\frac{2\pi}{\Lambda}\right)\right],$
(1)

where $k$ is the wavenumber of the PPSF, $L$ is the length of the PPSF,
subscripts $p,s,i$ denote pump, signal and idler respectively and $\Lambda$ is
the QPM period. The angular frequencies of photons obey energy conservation:
$\omega_{s}+\omega_{i}=\omega_{p}$ and we assume $\omega_{i}>\omega_{s}$.
Subscripts $A$, $B$ and $C$ represent the polarization modes of the photons.
In the context of this letter, we discuss the type-II SPDC in PPSF, in which a
pair of orthogonally polarized photons are generated by the down-conversion of
a vertically polarized pump photon, i.e. $A=V$[23]. Therefore, in type-II
SPDC, subscripts $B,C$ can be $H,V$ or $V,H$, where $H$ is for horizontally
polarized photons and $V$ is for vertically polarized photons. We assume the
PPSF is cw-pumped and $k_{A}(\omega_{p})=k_{V}(\omega_{p})\equiv k_{p}$, thus
the QPM condition becomes:

$\displaystyle
k_{p}-k_{H}(\omega_{p}/2)-k_{V}(\omega_{p}/2)-\frac{2\pi}{\Lambda}=0.$ (2)

Taylor-expanding the wavenumbers $k(\omega)$ in Eq. (1) about $\omega_{p}/2$
up to the second-order, and substituting Eq. (2) into Eq. (1) to eliminate the
zeroth order terms, we obtain[24]:

$\displaystyle
I(\Delta)\propto\mathrm{sinc}^{2}\left[\frac{1}{2}ML\Delta+\frac{1}{2}k_{2}L\Delta^{2}+O(\Delta^{3})\right],$
(3)

where $\Delta=\omega_{p}/2-\omega_{s}=\omega_{i}-\omega_{p}/2$,
$k_{2}=\partial^{2}k(\omega)/\partial\omega^{2}|_{\omega=\omega_{p}/2}$ is the
chromatic dispersion at frequency $\omega_{p}/2$, $M=(\partial
k_{H}(\omega)/\partial\omega-\partial
k_{V}(\omega)/\partial\omega)|_{\omega=\omega_{p}/2}$ is the group velocity
mismatch between H and V polarizations, and $O(\Delta^{3})$ represents the
terms that have orders 3 or more. The width of $I(\Delta)$ has an inverse
relation to $M$ and $k_{2}$. If $M$ and $k_{2}$ are small enough, the spectral
bandwidth of SPDC can be very broad. In general, the SPDC bandwidth in second-
order nonlinear crystals such as lithium niobate and potassium titanyl
phosphate is significantly limited by their high group birefringence $M$ and
nontrivial chromatic dispersion $k_{2}$. On the other hand, the group
birefringence $M$ in PPSF has been shown to be negligible[24] and the
polarization entanglement of the biphotons in PPSF can be naturally generated
without the need of any birefringence compensation[25]. As a result, the
bandwidth of the biphotons in PPSF sources is mainly determined by its
chromatic dispersion $k_{2}$, and $\Delta\propto 1/\sqrt{k_{2}L}$. Taking
advantage of its low dispersion at O-band, the PPSF is able to generate
entangled photons with very broad bandwidth.

The PPSF we use in the source is a 20-cm-long, weakly birefringent step-index
silica fiber with an NA $\approx$ 0.14 (at the wavelength of 1.55 $\mu$m),
which is compatible with telecom fibers such as SMF-28[26]. It exhibits
second-order nonlinearity which is induced through thermal poling. The
fabrication details of the PPSF are discussed in Ref.[27]. The QPM condition
is achieved through periodic UV erasure with $\Lambda=54\ \mu m$. As shown by
the experimentally measured second harmonic generation (SHG) spectrum in
Fig.1(a), the PPSF supports three types of SHG, and correspondingly three
types of SPDC[23]. The conversion efficiency is estimated to be $0.70\%/W$ for
type-0 SHG and $0.16\%/W$ for type-II SHG. The theoretical ratio of the three
peaks (Type 0, I, II) should be 9:1:4[28]. The experimental type-II peak is a
bit lower than 4/9 of the type 0 peak, which can be attributed to the
imprecise polarization alignment of the fundamental light in the SHG
measurement. Among the three types, the type-II SPDC in PPSF can be used for
compensation-free broadband polarization entanglement generation[24]. A finite
element eigenmode solver (Lumerical Inc.) is used for calculating the
birefringence and dispersion of the fiber modes based on the PPSF’s geometry.
Assuming a cw-pump is used, we simulate the type-II SPDC spectrum and obtain
the tuning curve as a function of the pump wavelength, as shown in Fig.1(b).
When the pump wavelength for SPDC is set at around the type-II SHG peak (653.3
nm), the PPSF can generate broadband biphotons with more than 130 nm
bandwidth.

Figure 1: (a) Experimentally measured and theoretically simulated SHG spectra
of the PPSF. The solid-line curves have their width based on the dispersion of
the fiber, while their heights are the best fit to the experimental data. The
weak birefringence in PPSF results in the spectral separation of three
polarization-dependent phase-matchings. (b) Theoretical tuning curve of the
type-II SPDC emission spectrum in PPSF with respect to the pump wavelength.
(c) Experimentally measured biphoton spectrum shows a biphoton emission
bandwidth greater than 130 nm ($>$ 24 THz). Figure 2: (a) Experimental setup
for the Hong-Ou-Mandel interference Measurement. LD: cw laser diode with
emission wavelength at 653 nm. SPD, single photon detector (IDQ220, ID
Quantique, quantum efficiency $\sim 20\%$ in O-band); TIA, time interval
analyzer (Hydraharp 400). (b) Hong-Ou-Mandel interference shows a dip of 83.2
$\pm$ 0.3 $\%$ visibility with width of 26.6 $\pm$ 1.3 fs.

The biphoton spectrum of type-II SPDC in PPSF is experimentally measured with
a pump laser at 653.3 nm at room temperature ($\sim 22^{o}C$), as shown in
Fig.1(c). To measure the biphoton spectrum, we first use a pair of fine
tunable filters at O-band (O/E land Inc., tuning range 1260 nm -1360 nm).
Outside the tuning range of the fine tunable filters, we use two coarse
wavelength division multiplexers (CWDMs, each has a 3dB transmission bandwidth
of 17nm) centered at 1370 nm and 1390 nm respectively. After calibrating the
wavelength-dependent loss and the detector efficiencies, a spectral bandwidth
of more than 130 nm (>24 THz in frequency) of type-II SPDC is obtained from
the measured coincidence counts.

In addition to the direct spectral brightness measurement, a Hong-Ou-Mandel
interference (HOMI) experiment is also performed, as one may use the temporal
correlation[29] of the biphotons to infer their bandwidth. The HOMI
experimental setup is shown in Fig.2(a). A laser diode that has its wavelength
stabilized at 653.3 nm by a fiber Bragg grating is used as the pump, with its
polarization adjusted to align to the slow axis (defined as the V polarization
in PPSF[23]) of the PPSF at the fiber input. At the output end of the PPSF,
fiber-pigtailed pump suppression filters reduce the pump power by >90 dB, at
an insertion loss of 6 dB for the down-converted light. The biphotons then
pass through an interferometer which is composed of a polarizing beam
splitter, an inline controllable delay line (General Photonics Inc. MDL-001),
a polarization controller, and a 50:50 beam splitter. The coincidence rates
are depicted in Fig.2(b). An HOMI dip of 26.6 $\pm$ 1.3 fs in width and
$83.2\pm 0.3\%$ in visibility is obtained from the fitting curve[30] by
minimizing the error with respect to the interference pattern. Note that, the
interference visibility is limited by the non-optimal components in the
interferometer which are designed to operate at 1550 nm instead of the telecom
O-band. Yet the dip visibility still well exceeds the classical limit. The dip
width indicates that the bandwidth of biphotons is 138 nm if the biphotons are
transform-limited. The dip width agrees well with our spectral measurement,
which is expected because of the low dispersion in PPSF.

Another important and unique feature of the PPSF biphoton source is that it is
capable of generating polarization entanglement over much of its bandwidth
without any birefringence compensation. The polarization entanglement at
various wavelengths of the emission band is measured with the quantum state
tomography (QST)[31] experimental setup shown in Fig.3(a). To perform QST at
different conjugated wavelength pairs $\lambda_{s}$ and $\lambda_{i}$, three
different CWDM sets are used as wavelength splitters. The CWDMs of 17 nm
bandwidth in each set were cascaded such that conjugated wavelengths near the
center wavelengths (shown in Table.1) would be transmitted. The biphoton
polarization states are analyzed by two polarization analyzers (PAs, Hewlett
Packard 8169A). Each PA includes one polarizer and two waveplates. The
commercial PAs were designed for 1550 nm and therefore the retardances of the
waveplates were carefully calibrated for the transmission wavelengths of the
CWDMs at telecom O-band. The results of the QST are summarized in Table.1,
which shows the concurrences (without subtracting accidentals) of the biphoton
states of each wavelength pair. The density matrices of the biphotons states
are shown in Fig.3(b)-(d). Neither the measurement apparatus nor the optical
components of the source are optimal (they are all designed for 1550nm except
for the PPSF), yet we are able to obtain concurrences of more than 0.91 in the
biphoton emission band, even when the biphotons are more than 120 nm apart.

Figure 3: (a) Experimental setup for polarization state tomography. PC,
polarization controller; PSF, pump suppression filters; CWDMs, coarse
wavelength division multiplexers; WP, waveplate; Pol., polarizer. (b)-(d) The
real and imaginary part of the density matrices of the biphoton states that
are measured using CWDMs centered at (b) 1330 nm and 1290 nm (c) 1350 nm and
1270 nm; (d) 1370 nm, CWDM centered on 1250nm is not available to us. Instead
of using a second CWDM at 1250nm, we used the refection port of the 1370nm
CWDM, which has a broad reflection spectrum, for the idler’s measurement.
Table 1: The experimental results of the quantum state tomography: the
concurrence[21] and the fidelity to a maximally polarization-entangled
biphoton state that are measured using three CWDM sets at different
wavelengths. Each of the CWDM filters has a top-hat transmission profile and a
3 dB bandwidth of 17nm.

Wavelengths $\lambda_{s}$, $\lambda_{i}$ | Concurrence | Fidelity
---|---|---
1330 nm, 1290 nm | 0.9570 $\pm$ 0.0075 | 0.9779 $\pm$ 0.0037
1350 nm, 1270 nm | 0.9372 $\pm$ 0.0124 | 0.9658 $\pm$ 0.0063
1370 nm* | 0.9110 $\pm$ 0.0131 | 0.9546 $\pm$ 0.0065

  * *

See caption of Fig.3(d).

In summary, we have demonstrated a broadband polarization-entangled photon-
pair source in PPSF by exploiting type-II SPDC at telecom O-band. The cw-
pumped PPSF source emits highly time-correlated and high quality polarization-
entangled biphotons of more than 130 nm bandwidth. The concurrence of
polarization entanglement is measured to be greater than 0.91 even when the
signal-idler is greater than 120 nm apart. The O-band PPSF source can be
further optimized. For instance, the PPSF in the context of this letter has a
non-zero chromatic dispersion ($|k_{2}|\sim 2ps^{2}/km$) at the current QPM
wavelength. The biphoton emission spectrum can be potentially broadened to be
more than a few hundreds of nanometers if the QPM wavelength is tuned to be
closer to the zero-dispersion wavelength of the PPSF. Moreover, using better
components such as pump suppression filters and beam splitters with lower loss
and better performance will surely result in higher entanglement quality as
well.

This simple fiber-based source is compatible with existing fiber
infrastructure. Operating near the zero-dispersion wavelength of silica fiber,
the time-correlated and polarization entangled biphotons generated in this
source are expected to be robust against chromatic dispersion and polarization
mode dispersion in long-distance quantum fiber communication[32, 33, 34].
Through further development, we anticipate that the source can be used in
quantum applications such as wavelength-multiplexed quantum communication[35,
36, 19] and high precision quantum sensing[4, 7, 37, 5, 38, 39].

Funding. Natural Sciences and Engineering Research Council of Canada
(RGPIN-2019-07019, RGPAS-2019-00113, CREATE-484907-16), Mitacs Globalink
Research Award-Abroad, and US Army Award W911NF20-2-0242. The U.S. Government
has a copyright license in this work pursuant to a Cooperative Research and
Development Agreement with University of Toronto

Disclosures. The authors declare no conflicts of interest.

## References

  * [1] S. Slussarenko and G. J. Pryde, Applied Physics Reviews 6, 041303 (2019).
  * [2] P. G. Kwiat, K. Mattle, H. Weinfurter, A. Zeilinger, A. V. Sergienko, and Y. Shih, Physical Review Letters 75, 4337 (1995).
  * [3] Y. Zhang, F. S. Roux, T. Konrad, M. Agnew, J. Leach, and A. Forbes, Science advances 2, e1501165 (2016).
  * [4] F. Kaiser, P. Vergyris, D. Aktas, C. Babin, L. Labonté, and S. Tanzilli, Light: Science & Applications 7, 17163 (2018).
  * [5] M. B. Nasr, B. E. A. Saleh, A. V. Sergienko, and M. C. Teich, Phys. Rev. Lett. 91, 083601 (2003).
  * [6] H. C. Lim, A. Yoshizawa, H. Tsuchida, and K. Kikuchi, Optics express 16, 16052 (2008).
  * [7] A. Valencia, G. Scarcelli, and Y. Shih, Applied Physics Letters 85, 2655 (2004).
  * [8] J. A. Grieve, Y. Shi, H. S. Poh, C. Kurtsiefer, and A. Ling, Applied Physics Letters 114, 131106 (2019).
  * [9] T. Zhong, F. N. C. Wong, T. D. Roberts, and P. Battle, Opt. Express 17, 12019 (2009).
  * [10] T. Zhong, X. Hu, F. N. C. Wong, K. K. Berggren, T. D. Roberts, and P. Battle, Optics Letters 35, 1392 (2010).
  * [11] A. Martin, V. Cristofori, P. Aboussouan, H. Herrmann, W. Sohler, D. Ostrowsky, O. Alibart, and S. Tanzilli, Opt. Express 17, 1033 (2009).
  * [12] A. Martin, A. Issautier, H. Herrmann, W. Sohler, D. B. Ostrowsky, O. Alibart, and S. Tanzilli, New Journal of Physics 12, 103005 (2010).
  * [13] M. T. Liu and H. C. Lim, Optics Express 22, 23261 (2014).
  * [14] Y. Shi, S. M. Thar, H. S. Poh, J. A. Grieve, C. Kurtsiefer, and A. Ling, Applied Physics Letters 117, 124002 (2020).
  * [15] Z.-H. Xiang, J. Huwer, J. Skiba-Szymanska, R. M. Stevenson, D. J. P. Ellis, I. Farrer, M. B. Ward, D. A. Ritchie, and A. J. Shields, Communications Physics 3 (2020).
  * [16] M. A. Hall, J. B. Altepeter, and P. Kumar, Optics Express 17, 14558 (2009).
  * [17] M. B. Nasr, S. Carrasco, B. E. A. Saleh, A. V. Sergienko, M. C. Teich, J. P. Torres, L. Torner, D. S. Hum, and M. M. Fejer, Phys. Rev. Lett. 100, 183601 (2008).
  * [18] M. C. Booth, B. E. Saleh, and M. C. Teich, Optics Communications 284, 2542 (2011).
  * [19] S. K. Joshi, D. Aktas, S. Wengerowsky, M. Lončarić, S. P. Neumann, B. Liu, T. Scheidl, G. C. Lorenzo, Ž. Samec, L. Kling, A. Qiu, M. Razavi, M. Stipčević, J. G. Rarity, and R. Ursin, Science Advances 6, eaba0959 (2020).
  * [20] T. Kim, M. Fiorentino, and F. N. C. Wong, Phys. Rev. A 73, 012316 (2006).
  * [21] W. K. Wootters, Physical Review Letters 80, 2245 (1998).
  * [22] A. Christ, A. Fedrizzi, H. Hübel, T. Jennewein, and C. Silberhorn, _Single-Photon Generation and Detection: Chapter 11. Parametric Down-Conversion_ , vol. 45 (Elsevier Inc. Chapters, 2013).
  * [23] E. Y. Zhu, Z. Tang, L. Qian, L. G. Helt, M. Liscidini, J. E. Sipe, C. Corbari, A. Canagasabey, M. Ibsen, and P. G. Kazansky, Phys. Rev. Lett. 108, 213902 (2012).
  * [24] C. Chen, E. Y. Zhu, A. Riazi, A. V. Gladyshev, C. Corbari, M. Ibsen, P. G. Kazansky, and L. Qian, Optics Express 25, 22667 (2017).
  * [25] E. Y. Zhu, Z. Tang, L. Qian, L. G. Helt, M. Liscidini, J. E. Sipe, C. Corbari, A. Canagasabey, M. Ibsen, and P. G. Kazansky, Opt. Lett. 38, 4397 (2013).
  * [26] Corning, _Corning SMF-28 Optical Fibers_.
  * [27] A. Canagasabey, C. Corbari, A. V. Gladyshev, F. Liegeois, S. Guillemet, Y. Hernandez, M. V. Yashkov, A. Kosolapov, E. M. Dianov, M. Ibsen, and P. G. Kazansky, Optics Letters 34, 2483 (2009).
  * [28] E. Y. Zhu, L. Qian, L. G. Helt, M. Liscidini, J. E. Sipe, C. Corbari, A. Canagasabey, M. Ibsen, and P. G. Kazansky, Optics Letters 35, 1530 (2010).
  * [29] C. K. Hong, Z. Y. Ou, and L. Mandel, Phys. Rev. Lett. 59, 2044 (1987).
  * [30] A. M. Brańczyk, “Hong-ou-mandel interference,” (2017).
  * [31] D. F. V. James, P. G. Kwiat, W. J. Munro, and A. G. White, Phys. Rev. A 64, 052312 (2001).
  * [32] D. E. Jones, B. T. Kirby, and M. Brodsky, npj Quantum Information 4 (2018).
  * [33] M. Brodsky, E. C. George, C. Antonelli, and M. Shtaif, Optics Letters 36, 43 (2010).
  * [34] M. Shtaif, C. Antonelli, and M. Brodsky, Optics Express 19, 1728 (2011).
  * [35] S. Wengerowsky, S. K. Joshi, F. Steinlechner, H. Hübel, and R. Ursin, Nature 564, 225 (2018).
  * [36] E. Y. Zhu, C. Corbari, A. Gladyshev, P. G. Kazansky, H.-K. Lo, and L. Qian, Journal of the Optical Society of America B 36, B1 (2019).
  * [37] A. Riazi, C. Chen, E. Y. Zhu, A. V. Gladyshev, P. G. Kazansky, J. E. Sipe, and L. Qian, npj Quantum Information 5, 1 (2019).
  * [38] D. A. Kalashnikov, A. V. Paterova, S. P. Kulik, and L. A. Krivitsky, Nature Photonics 10, 98 (2016).
  * [39] A. Riazi, E. Y. Zhu, C. Chen, A. V. Gladyshev, P. G. Kazansky, and L. Qian, Optics letters 44, 1484 (2019).

sample


#  Possible benefit of longer $L^{*}$ for detectors at ILC

Yasuhiro Sugimoto111Talk presented at the International Workshop on Future
Linear Colliders (LCWS2021), 15 – 18 March, 2021. C21-03-15.1.
High Energy Accelerator Research Organization (KEK)
Tsukuba  Ibaraki 305-0801  Japan

###### Abstract

In the present design of ILC, $L^{*}$, the distance between the interaction
point (IP) and the front surface of the final focusing magnet (QD0), is 4.1 m.
The QD0 is supported from the detector platform by a cantilever type support
or from the detector itself. This design could cause several difficulties in
smooth operation of ILC or in maintenance of detectors. These difficulties
could be mitigated by adopting longer $L^{*}$ optics. In this article, we
discuss possible benefit of longer $L^{*}$ for detectors.

##  1 Introduction

In the design of International Linear Collider (ILC) [1], distance between the
interaction point and the front surface of the final focusing quadrupole
magnet, $L^{*}$, is one of the essential parameters of the accelerator. In the
baseline design, $L^{*}$ is 4.1 m [2]. The final focusing quadrupole magnets
(QD0) locate inside of the detector, and supported from the detector itself
(SiD) or from a cantilever support structure (ILD) [3]. In both cases, QD0 is
supported from the movable platform on which the detector is placed. In this
configuration, there are risks of;

  * •

QD0 vibration caused by the detector,

  * •

poor position repeatability of QD0 and longer time for machine tuning after
push-pull operation,

  * •

difficulty in opening detector endcap.

After publication of the ILC TDR [1], longer $L^{*}$ optics has been proposed
[4, 5, 6] and seriously studied for CLIC. In the recent CLIC design $L^{*}=6$
m is adopted. If we could adopt the similar optics for ILC, the risks listed
above would be greatly mitigated.

##  2 ILD endcap opening

The cut view of ILD detector is schematically shown in Figure 1 (left). QD0 is
supported from a cantilever structure standing on the movable platform.
Because the pillar of this structure standing on the movable platform locates
just behind the detector endcap, the rear part of the endcap has to be split
as shown in Figure 1 (right) in order to clear the pillar [7]. About 1.2 m gap
can be obtained between the endcap and the barrel part of the detector by
splitting the rear part of the endcap. However, if more gap is needed, for
example, to uninstall the central tracker, the QD0 support structure has to be
withdrawn by few meters. The split endcap requires additional engineering
challenges. Because each part of the split endcap needs own support legs, more
space on the floor is necessary to make it stable against earth quake.
Lowering method from surface assembly hall to the underground detector hall
using a gantry crane could be more complicated.

Figure 1: Cut view of ILD detector (left) and structure of its endcap (right).
The gray part below the detector in the left figure is the movable platform.

##  3 ILD with $L^{*}=6$ m

If $L^{*}=6$ m option can be adopted for ILC, it would bring a large benefit
for detectors. In this case, QD0 can be supported from the floor of the beam
tunnel as shown in Figure 2, and we can get rid of QD0 support pillar standing
on the movable platform. In order to make the push-pull operation possible,
QD0 should be retractable using a sliding support like QCS of SuperKEKB [8].
Because the QD0 support pillar does not exist in this design, the endcap of
ILD does not have to be split. The endcap can be easily opened at the
maintenance position when a barrel part detector has to be uninstalled.

Figure 2: ILD with $L^{*}=6$ m when the endcap is closed (top) and
open(bottom).

Another merit of longer $L^{*}$ option could be reduction of beam background
due to back-scattering of $e^{+}/e^{-}$ pair-background from the small angle
calorimeter (BCAL) or QD0. The small angle calorimeter, BCAL, is supposed to
be placed near the front surface of QD0. If $L^{*}$ becomes longer, BCAL can
be placed farther from the interaction point where the magnetic field caused
by the detector solenoid is much weaker. Because the back-scattered
$e^{+}/e^{-}$ goes back to the central detector region spiraling along the
magnetic field line, the number of back-scattered particles reaching the
central detectors would largely reduced if the source is located at the weak
magnetic field region. In the ILD baseline design, an anti-DID (Detector-
Integrated-Dipole) is used to guide the dense part of pair background
particles from the interaction point to the beam holes of the BCAL and QD0
along the magnetic field line. On the other hand, if the magnetic field around
the BCAL and QD0 is weak, this anti-DID may not work, and increase number of
background particles hitting the BCAL and QD0. We need a detailed simulation
study of the background to see if the back-scattered background can be
reduced. If the result is that the anti-DID does not work, but the
backscattered background is reduced, then we can discard the anti-DID, and
reduce the cost, construction period, and risks.

In addition to the position of BCAL, some modification of ILD is needed. For
the push-pull operation, the beam pipe has to be disconnected at $z\sim 6$ m.
In order to make access to flanges at $z\sim 6$ m possible, the hole of the
endcap has to be enlarged there. The remote vacuum connection (RVC) adopted
for SuperKEKB could be another solution.

The longer $L^{*}$ option is also preferable from the viewpoint of smooth
operation of ILC. QD0 supported from the floor of the beam tunnel is much more
stable against the vibration than that supported from the support pillar
standing on the movable detector platform. Much better position repeatability
of QD0 can be achieved after push-pull operation. In the case of the QD0
support from the movable platform, the anticipated repeatability is $\sim 0.5$
mm. On the other hand, in the case of the sliding support on the floor of the
beam tunnel, we can expect to achieve the position repeatability of few tens
of $\mu$m from the experience in SuperKEKB. The better repeatability would
make the time for machine tuning after push-pull operation much faster, which
could compensate possible luminosity reduction in longer $L^{*}$ optics.

##  4 Summary

The design of QD0 support in TDR has possible risks in stable and smooth
operation of ILC, as well as difficulties in detector design and maintenance.
The QD0 support from the beam tunnel with longer $L^{*}$ could solve these
issues. The longer $L^{*}$ option might also contribute to reduction of cost
and possibly construction period of ILD detector. Therefore, this option
should be seriously studied during early phase of Pre-Lab period, both from
the accelerator and detector point of view.

## References

  * [1] C. Adolphsen (ed.) et al., “The International Linear Collider Technical Design Report-Volume 3.II: Accelerator Baseline Design”, arXiv:1306.6328[physics.acc-ph] (2013).
  * [2] K. Busser, T. Markiewicz, N. Terunuma, N. Walker, G. White, “Change Review Panel for ILC-CR-002, a single $L^{*}$ Close-out / recommendations”, talk presented at Asian Linear Collider Workshop (ALCW2015), April 19-24, 2015.
  * [3] T. Behnke (ed.) et al., “The International Linear Collider Technical Design Report-Volume 4: Detectors”, arXiv:1306.6329[physics.ins-det] (2013).
  * [4] T. Okugi, “Large $L*$ for ILC”, talk presented at Americas Workshop on Linear Colliders 2014 (AWLC2014), May 12-16, 2014.
  * [5] F. Plassard, “Longer $L^{*}$ for ILC”, Master Thesis, Feb. 2015.
  * [6] F. Plassard, “Longer $L^{*}$ for CLIC 380”, PhD Thesis, Jul. 2018.
  * [7] K. Sinram, “How to open the detectors”, talk presented at Mini-Workshop on Infrastructure and CFS for Physics and Detectors, Feb. 27, 2019.
  * [8] H. Yamaoka, et al., “Design and construction of the QCS moving stage” (in Japanese), Proceedings of the 12th Annual Meeting of Particle Accelerator Society of Japan, Aug.5-7, 2015.


Finally, differentiating (4.37b) with respect to $x$, we have

$\displaystyle\displaystyle\Phi_{xxxx}=\Phi_{xxt}-a\varphi_{xxx}+b\Phi_{xx},$

and thus

$\displaystyle\displaystyle\|\Phi_{xxxx}\|^{2}\leq
C\|(\Phi_{xx},\Phi_{xxt},\varphi_{xxx})\|^{2}\leq
C\left(\|\varphi_{0}\|_{3}^{2}+\|\psi_{0}\|_{2}^{2}+\|\Phi_{0}\|_{4}^{2}\right).$

The proof of Proposition 4.2 is complete. $\square$

###  4.5. Proof of Theorem 2.2

In view of Proposition 4.2, the problem (1.5a)–(1.5c), (1.7)–(1.8) admits a
unique classical solution $(\rho,m,\phi)$ in $\mathbb{R}_{+}\times(0,\infty)$.
Moreover, thanks to (4.2), (4.7) and (4.8), it holds that

$\displaystyle\displaystyle\|(\rho-\bar{\rho},m)\|_{2}^{2}+\|\phi-\bar{\phi}\|_{4}^{2}\leq
C\left(\|\varphi_{0}\|_{3}^{2}+\|\psi_{0}\|_{2}^{2}+\|\Phi_{0}\|_{4}^{2}\right),$

and that

$\displaystyle\displaystyle\int_{0}^{t}\left(\|(\rho-\bar{\rho},m)\|_{2}^{2}+\|\phi-\bar{\phi}\|_{3}^{2}+\|(\rho_{\tau},m_{\tau},\phi_{\tau})\|_{1}^{2}\right)\mathrm{d}\tau\leq
C\left(\|\varphi_{0}\|_{3}^{2}+\|\psi_{0}\|_{2}^{2}+\|\Phi_{0}\|_{4}^{2}\right)$
(4.101)

for any $t>0$. In the following, we shall prove the large time behavior of
$(\rho,m,\phi)$ as in (2.5). For this, recalling the Sobolev inequality
$\|f\|_{L^{\infty}}\leq C\|f\|^{\frac{1}{2}}\|f_{x}\|^{\frac{1}{2}}$, it
suffices to show that

$\displaystyle\displaystyle\lim_{t\rightarrow\infty}\|(\rho-\bar{\rho},m,\phi-\bar{\phi})(\cdot,t)\|^{2}\rightarrow
0.$ (4.102)

In fact, with the help of (4.101) and Cauchy-Schwarz inequality, we get

$\displaystyle\displaystyle\int_{0}^{+\infty}\left|\frac{\mathrm{d}}{\mathrm{d}t}\|(\rho-\bar{\rho},m,\phi-\bar{\phi})(\cdot,t)\|^{2}\right|\mathrm{d}t$
$\displaystyle~{}\displaystyle\leq
C\int_{0}^{+\infty}\left(\|(\rho-\bar{\rho},m,\phi-\bar{\phi})\|^{2}+\|(\rho_{t},m_{t},\phi_{t})\|^{2}\right)\mathrm{d}t\leq\infty.$
(4.103)

The estimate (4.101) in combination with (4.5) gives (4.102). Then (2.5) is
proved and we complete the proof of Theorem 2.2. $\square$

## Acknowledgement

G. Hong is partially supported from the CAS AMSS-POLYU Joint Laboratory of
Applied Mathematics postdoctoral fellowship scheme. H.Y. Peng was supported
from the National Natural Science Foundation of China (No. 11901115), Natural
Science Foundation of Guangdong Province (No. 2019A1515010706). Z.-A. Wang was
supported in part by the Hong Kong RGC GRF grant No. PolyU 153055/18P
(P0005472) and an internal grant No. ZZKN from HKPU (P0031013). C.J. Zhu was
supported by the National Natural Science Foundation of China (No. 11771150,
11831003 and 11926346) and Guangdong Basic and Applied Basic Research
Foundation (No. 2020B1515310015).

## References

  * [1] D. Ambrosi, F. Bussolino, and L. Preziosi, A review of vasculogenesis models, J. Theore. Med., 6 (2005), pp. 1–19.
  * [2] F. Berthelin, D. Chiron, and M. Ribot, Stationary solutions with vacuum for a one-dimensional chemotaxis model with nonlinear pressure, Comm. Math. Sci., 14 (2016), pp. 147–186.
  * [3] J. Carrillo, X. Chen, Q. Wang, Z. Wang, and L. Zhang, Phase transitions and bump solutions of the Keller-Segel model with volume exclusion, SIAM J. Appl. Math., 80 (2020), pp. 232–261.
  * [4] J.-A. Carrillo, J.-Y. Li, and Z.-A. Wang, Boundary spike-layer solutions of the singular Keller-Segel system: existence and stability, Proc. London Math. Soc., Doi:10.1112/plms.12319, 2020.
  * [5] S. Chandrasekhar, An introduction to the study of stellar structure, vol. 2, Courier Corporation, 1957.
  * [6] P.-H. Chavanis, Jeans type instability for a chemotactic model of cellular aggregation, Eur. Phys. J. B, 52 (2006), pp. 433–443.
  * [7] P.-H. Chavanis and C. Sire, Kinetic and hydrodynamic models of chemotactic aggregation, Physica A, 384 (2007), pp. 199–222.
  * [8] A. Choudhuri, The physics of fluids and plasmas: an introduction for astrophysicists, Cambridge University Press, 1998.
  * [9] C. Di Russo, Analysis and numerical approximations of hydrodynamical models of biological movements, Rend. Mat. Appl. (7), 32 (2012), pp. 117–367.
  * [10] C. Di Russo, Existence and asymptotic behavior of solutions to a semilinear hyperbolic-parabolic model of chemotaxis, Indiana Univ. Math. J., 65 (2016), pp. 493–533.
  * [11] C. Di Russo and A. Sepe, Existence and asymptotic behavior of solutions to a quasi-linear hyperbolic-parabolic model of vasculogenesis, SIAM J. Math. Anal., 45 (2013), pp. 748–776.
  * [12] F. Filbet and C.-W. Shu, Approximation of hyperbolic models for chemosensitive movement, SIAM J. Sci. Comput., 27 (2005), pp. 850–872.
  * [13] A. Gamba, D. Ambrosi, A. Coniglio, A. De Candia, S. Di Talia, E. Giraudo, G. Serini, L. Preziosi, and F. Bussolino, Percolation, morphogenesis, and burgers dynamics in blood vessels formation, Phys. Rev. Lett., 90 (2003), p. 118101.
  * [14] L. Hsiao and T.-P. Liu, Convergence to nonlinear diffusion waves for solutions of a system of hyperbolic conservation laws with damping, Comm. Math. Phys., 143 (1992), pp. 599–605.
  * [15] F.-M. Huang, M. Mei, Y. Wang, and H.-M. Yu, Asymptotic convergence to stationary waves for unipolar hydrodynamic model of semiconductors, SIAM J. Math. Anal., 43 (2011), pp. 411–429.
  * [16] R. Kowalczyk, A. Gamba, and L. Preziosi, On the stability of homogeneous solutions to some aggregation models, Disc. Cont. Dyn. Syst. Series B, 4 (2004), pp. 203–220.
  * [17] D. Li, T. Li, and K. Zhao, On a hyperbolic-parabolic system modeling chemotaxis, Math. Models Meth. Appl. Sci., 21 (2011), pp. 1631–1650.
  * [18] T. Li and Z.-A. Wang, Nonlinear stability of traveling waves to a hyperbolic-parabolic system modeling chemotaxis, SIAM J. Appl. Math., 70 (2010), pp. 1522–1541.
  * [19] C.-K. Lin, C.-T. Lin, and M. Mei, Asymptotic behavior of solution to nonlinear damped $p$-system with boundary effect, Int. J. Numer. Anal. Model. Ser. B, 1 (2010), pp. 70–92.
  * [20] H.-F. Ma and M. Mei, Best asymptotic profile for linear damped $p$-system with boundary effect, J. Differential Equations, 249 (2010), pp. 446–484.
  * [21] P. Marcati, M. Mei, and B. Rubino, Optimal convergence rates to diffusion waves for solutions of the hyperbolic conservation laws with damping, J. Math. Fluid Mech., 7 (2005), pp. S224–S240.
  * [22] P. Markowich, C. Ringhofer, and C. Schmeiser, Semiconductor equations, Springer Science & Business Media, 2012.
  * [23] A. Matsumura, Global existence and asymptotics of the solutions of the second-order quasilinear hyperbolic equations with the first-order dissipation, Publ. Res. Inst. Math. Sci., 13 (1977/78), pp. 349–379.
  * [24] M. Mei, H. Peng, and Z.-A. Wang, Asymptotic profile of a parabolic-hyperbolic system with boundary effect arising from tumor angiogenesis, J. Differential Equations, 259 (2015), pp. 5168–5191.
  * [25] K. Nishihara, Convergence rates to nonlinear diffusion waves for solutions of system of hyperbolic conservation laws with damping, J. Differential Equations, 131 (1996), pp. 171–188.
  * [26] K. Nishihara and T. Yang, Boundary effect on asymptotic behaviour of solutions to the $p$-system with linear damping, J. Differential Equations, 156 (1999), pp. 439–458.
  * [27] M. Zhang and C. Zhu, Global existence of solutions to a hyperbolic-parabolic system, Proc. Amer. Math. Soc., 135 (2007), pp. 1017–1027.