# Finite Sample Prediction and Recovery Bounds for Ordinal Embedding

Lalit Jain, University of Wisconsin-Madison
Kevin Jamieson, University of California, Berkeley
Robert Nowak, University of Wisconsin-Madison

###### Abstract

The goal of ordinal embedding is to represent items as points in a low-
dimensional Euclidean space given a set of constraints in the form of distance
comparisons like “item $i$ is closer to item $j$ than item $k$”. Ordinal
constraints like this often come from human judgments. To account for errors
and variation in judgments, we consider the noisy situation in which the given
constraints are independently corrupted by reversing the correct constraint
with some probability. This paper makes several new contributions to this
problem. First, we derive prediction error bounds for ordinal embedding with
noise by exploiting the fact that the rank of a distance matrix of points in
$\mathbb{R}^{d}$ is at most $d+2$. These bounds characterize how well a
learned embedding predicts new comparative judgments. Second, we investigate
the special case of a known noise model and study the Maximum Likelihood
estimator. Third, knowledge of the noise model enables us to relate prediction
errors to embedding accuracy. This relationship is highly non-trivial since we
show that the linear map corresponding to distance comparisons is non-
invertible, but there exists a nonlinear map that is invertible. Fourth, two
new algorithms for ordinal embedding are proposed and evaluated in
experiments.

##  1 Ordinal Embedding

Ordinal embedding, also known as non-metric multidimensional scaling, aims to
represent items as points in $\mathbb{R}^{d}$ so that the distances between
items agree as well as possible with a given set of ordinal comparisons such
as item $i$ is closer to item $j$ than to item $k$. This is a classic problem
that is often used to visualize perceptual similarities [1, 2]. Recently,
several authors have proposed a variety of new algorithms for learning a
metric embedding from ordinal information [3, 4, 5, 6, 7]. There has also been
some theoretical progress towards characterizing the consistency of ordinal
embedding methods. For example, it has been shown that the correct embedding
can be learned in the limit as the number of items grows [8, 9, 10]. However,
a major shortcoming of all prior work is the lack of generalization and
embedding error bounds for problems involving a finite number of items and
observations. This paper addresses this problem, developing error bounds for
ordinal embedding algorithms with known observation models. The bounds
explicitly show the dependence on the number of ordinal comparisons relative
to the number of items and the dimension of the embedding. In addition, we
propose two new algorithms for recoverying embeddings: the first is based on
unbiasing a nuclear norm constrained optimization and the second is based on
projected gradient descent onto the space of rank-$d$ matrices, commonly
referred to as hard-thresholding. Both methods match state-of-the-art
performance while being simpler to implement and faster to converge.

###  1.1 Ordinal Embedding from Noisy Data

Consider $n$ points
$\boldsymbol{x}_{1},\boldsymbol{x}_{2},\dots,\boldsymbol{x}_{n}\in\mathbb{R}^{d}$.
Let
$\boldsymbol{X}=[\boldsymbol{x}_{1}\cdots\boldsymbol{x}_{n}]\in\mathbb{R}^{d\times
n}$. The Euclidean distance matrix $\boldsymbol{D}^{\star}$ is defined to have
elements $D_{ij}^{\star}=\|\boldsymbol{x}_{i}-\boldsymbol{x}_{j}\|_{2}^{2}$.
Ordinal embedding is the problem of recovering $\boldsymbol{X}$ given ordinal
constraints on distances. This paper focuses on “triplet” constraints of the
form $D_{ij}^{\star}<D_{ik}^{\star}$, where $1\leq i\neq j\neq k\leq n$.
Furthermore, we only observe noisy indications of these constraints, as
follows. Each triplet $t=(i,j,k)$ has an associated probability $p_{t}$
satisfying

$p_{t}>1/2\ \Longleftrightarrow\
\|\boldsymbol{x}_{i}-\boldsymbol{x}_{j}\|^{2}<\|\boldsymbol{x}_{i}-\boldsymbol{x}_{k}\|^{2}\
.$

Let ${\cal S}$ denote a collection of triplets drawn independently and
uniformly at random. And for each $t\in{\cal S}$ we observe an independent
random variable $y_{t}=-1$ with probability $p_{t}$, and $y_{t}=1$ otherwise.
The goal is to recover the embedding $\boldsymbol{X}$ from these data. Exact
recovery of $\boldsymbol{D}^{\star}$ from such data requires a known link
between $p_{t}$ and $\boldsymbol{D}^{\star}$. To this end, our main focus is
the following problem.

Ordinal Embedding from Noisy Data

Consider $n$ points
$\boldsymbol{x}_{1},\boldsymbol{x}_{2}\cdots,\boldsymbol{x}_{n}$ in
$d$-dimensional Euclidean space. Let ${\cal S}$ denote a collection of
triplets and for each $t\in{\cal S}$ observe an independent random variable
$y_{t}\ =\ \left\\{\begin{array}[]{ll}-1&w.p.\
f(D_{ij}^{\star}-D_{ik}^{\star})\\\ \\\ 1&w.p.\
1-f(D_{ij}^{\star}-D_{ik}^{\star})\end{array}\right.\ .$ where the link
function $f:\mathbb{R}\rightarrow[0,1]$ is known. Estimate $\boldsymbol{X}$
from ${\cal S}$, $\\{y_{t}\\}$, and $f$.

For example, if $f$ is the logistic function, then for triplet $t=(i,j,k)$

$\displaystyle p_{t}=\mathbb{P}(y_{t}=-1)\ =\
f(D_{ij}^{\star}-D_{ik}^{\star})\ =\
\frac{1}{1+\exp(D_{ij}^{\star}-D_{ik}^{\star})}\ ,$ (1)

then $D_{ij}^{\star}-D_{ik}^{\star}=\log\big{(}\tfrac{1-p_{t}}{p_{t}}\big{)}$.
However, we stress that we only require the existence of a link function for
exact recovery of $\boldsymbol{D}^{\star}$. Indeed, if one just wishes to
predict the answers to unobserved triplets, then the results of Section 2 hold
for arbitrary $p_{t}$ probabilities. We note that a problem known as one-bit
matrix completion has similarly used link functions to recover structure [11].
However, while that work made direct measurements of the entries of the
matrix, in this work we observe linear projections and as we will see later,
the collection of these linear operators has a a non-empty kernel creating
non-trivial challenges.

###  1.2 Organization of Paper

This paper takes the following approach to ordinal embedding. First we derive
prediction error bounds for ordinal embedding with noise in Section 2. These
bounds exploit the fact that the rank of a distance matrix of points in
$\mathbb{R}^{d}$ is at most $d+2$. Then we consider the special case of a
known observation model and the Maximum Likelihood estimator in Section 3. The
link function enables us to relate prediction errors to error bounds on
estimates of differences $\\{D_{ij}^{\star}-D_{ik}^{\star}\\}$. In Section 4,
we study the non-trivial problem of recovering $\boldsymbol{D}^{\star}$, and
thus $\boldsymbol{X}$, from the $\\{D_{ij}^{\star}-D_{ik}^{\star}\\}$. Lastly,
in Section 5, two new algorithms for ordinal embedding are proposed and
experimentally evaluated.

###  1.3 Notation and Assumptions

We will use $(\boldsymbol{D}^{\star},\boldsymbol{G}^{\star})$ to denote the
distance and Gram matrices of the latent embedding, and
$(\boldsymbol{D},\boldsymbol{G})$ to denote an arbitrary distance matrix and
its corresponding Gram matrix. The observations $\\{y_{t}\\}$ carry
information about $\boldsymbol{D}^{\star}$, but distance matrices are
invariant to rotation and translation, and therefore it may only be possible
to recover $\boldsymbol{X}$ up to a rigid transformation. Therefore, we make
the following assumption throughout the paper.

######  Assumption 1.

To eliminate the translational ambiguity, assume the points
$\boldsymbol{x}_{1},\dots\boldsymbol{x}_{n}\in\mathbb{R}^{d}$ are centered at
the origin (i.e., $\sum_{i=1}^{n}\boldsymbol{x}_{i}={\bf 0}$).

Define the centering matrix
$\boldsymbol{V}:=\boldsymbol{I}-\frac{1}{n}\mathbf{1}\mathbf{1}^{T}$. Note
that under the above assumption,
$\boldsymbol{X}\boldsymbol{V}=\boldsymbol{X}$. Note that
$\boldsymbol{D}^{\star}$ is determined by the Gram matrix
$\boldsymbol{G}^{\star}=\boldsymbol{X}^{T}\boldsymbol{X}$. In addition,
$\boldsymbol{X}$ can be determined from $\boldsymbol{G}$ up to a unitary
transformation. Furthermore, we will assume that the Gram matrix is “centered”
so that $\boldsymbol{V}\boldsymbol{G}\boldsymbol{V}=\boldsymbol{G}$. Centering
is equivalent to assuming the underlying points are centered at the origin
(e.g., note that
$\boldsymbol{V}\boldsymbol{G}^{\star}\boldsymbol{V}=\boldsymbol{V}\boldsymbol{X}^{T}\boldsymbol{X}\boldsymbol{V}=\boldsymbol{X}^{T}\boldsymbol{X}$).
It will be convenient in the paper to work with both the distance and Gram
matrix representations, and the following identities will be useful to keep in
mind. For any distance matrix $\boldsymbol{D}$ and its centered Gram matrix
$\boldsymbol{G}$

$\displaystyle\boldsymbol{G}$ $\displaystyle=$
$\displaystyle\boldsymbol{V}\boldsymbol{D}\boldsymbol{V}\ ,$ (2)
$\displaystyle\boldsymbol{D}$ $\displaystyle=$
$\displaystyle\mbox{diag}(\boldsymbol{G})\boldsymbol{1}^{T}-2\boldsymbol{G}+\boldsymbol{1}\mbox{diag}(\boldsymbol{G})^{T}\
,$ (3)

where $\mbox{diag}(\boldsymbol{G})$ is the column vector composed of the
diagonal of $\boldsymbol{G}$. In particular this establishes a bijection
between centered Gram matrices and distance matrices. We refer the reader to
[12] for an insightful and thorough treatment of the properties of distance
matrices. We also define the set of all unique triplets

${\cal T}\ :=\ \big{\\{}(i,j,k)\,:\,1\leq i\neq j\neq k\leq n,j<k\big{\\}}\ .$

######  Assumption 2.

The observed triplets in ${\cal S}$ are drawn independently and unifomly from
${\cal T}$.

##  2 Prediction Error Bounds

For $t\in{\cal T}$ with $t=(i,j,k)$ we define $L_{t}$ to be the linear
operator satisfying
$L_{t}(\boldsymbol{X}^{T}\boldsymbol{X})=\|x_{i}-x_{j}\|^{2}-\|x_{i}-x_{k}\|^{2}$
for all $t\in{\cal T}$. In general, for any Gram matrix $\boldsymbol{G}$

$L_{t}(\boldsymbol{G})\ :=\ G_{jj}-2G_{ij}-G_{kk}+2G_{ik}.$

We can naturally view $L_{t}$ as a linear operator on $\mathbb{S}^{n}_{+}$,
the space of $n\times n$ symmetric positive semidefinite matrices. We can also
represent $\boldsymbol{L}_{t}$ as a symmetric $n\times n$ matrix
$\boldsymbol{L}_{t}$ that is zero everywhere except on the submatrix
corresponding to $i,j,k$ which has the form

$\left[\begin{array}[]{rrr}0&-1&1\\\ -1&1&0\\\ 1&0&-1\end{array}\right]$

and then

$L_{t}(\boldsymbol{G})\ :=\ \langle\boldsymbol{L}_{t},\boldsymbol{G}\rangle\ $

where $\langle A,B\rangle=\text{vec}(A)^{T}\text{vec}(B)$ for any compatible
matrices $A,B$. Ordering the elements of $\mathcal{T}$ lexicographically, we
arrange all the $\boldsymbol{L}_{t}(\boldsymbol{G})$ together to define the
$n{n-1\choose{2}}$-dimensional vector

$\displaystyle\mathcal{L}(\boldsymbol{G})=[\boldsymbol{L}_{123}(\boldsymbol{G}),\boldsymbol{L}_{124}(\boldsymbol{G}),\cdots,\boldsymbol{L}_{ijk}(\boldsymbol{G}),\cdots]^{T}.$
(4)

Let $\ell(y_{t}\langle\boldsymbol{L}_{t},\boldsymbol{G}\rangle)$ denote a loss
function. For example we can consider the $0-1$ loss
$\ell(y_{t}\langle\boldsymbol{L}_{t},\boldsymbol{G}\rangle)=\mathds{1}_{\\{\text{sign}\\{y_{t}\langle\boldsymbol{L}_{t},\boldsymbol{G}\rangle\\}\neq
1\\}}$, the hinge-loss
$\ell(y_{t}\langle\boldsymbol{L}_{t},\boldsymbol{G}\rangle)=\max\\{0,1-y_{t}\langle\boldsymbol{L}_{t},\boldsymbol{G}\rangle\\}$,
or the logistic loss

$\displaystyle\ell(y_{t}\langle\boldsymbol{L}_{t},\boldsymbol{G}\rangle)=\log(1+\exp(-y_{t}\langle\boldsymbol{L}_{t},\boldsymbol{G}\rangle)).$
(5)

Let $p_{t}:=\mathbb{P}(y_{t}=-1)$ and take the expectation of the loss with
respect to both the uniformly random selection of the triple $t$ and the
observation $y_{t}$, we have the risk of $\boldsymbol{G}$

$\displaystyle R(\boldsymbol{G})$ $\displaystyle:=$
$\displaystyle\mathbb{E}[\ell(y_{t}\langle\boldsymbol{L}_{t},\boldsymbol{G}\rangle)]=\frac{1}{|{\cal
T}|}\sum_{t\in{\cal
T}}p_{t}\ell(-\langle\boldsymbol{L}_{t},\boldsymbol{G}\rangle)+(1-p_{t})\ell(\langle\boldsymbol{L}_{t},\boldsymbol{G}\rangle).$

Given a set of observations ${\cal S}$ under the model defined in the problem
statement, the empirical risk is,

$\displaystyle\widehat{R}_{\cal S}(\boldsymbol{G})=\frac{1}{|{\cal
S}|}\sum_{t\in{\cal
S}}\ell(y_{t}\langle\boldsymbol{L}_{t},\boldsymbol{G}\rangle)$ (6)

which is an unbiased estimator of the true risk: $\mathbb{E}[\widehat{R}_{\cal
S}(\boldsymbol{G})]=R(\boldsymbol{G})$. For any
$\boldsymbol{G}\in\mathbb{S}^{n}_{+}$, let $\|\boldsymbol{G}\|_{*}$ denote the
nuclear norm and
$\|\boldsymbol{G}\|_{\infty}:=\max_{ij}|\boldsymbol{G}_{ij}|$. Define the
constraint set

$\displaystyle{\cal G}_{\lambda,\gamma}\ :=\
\\{\boldsymbol{G}\in\mathbb{S}^{n}_{+}:\|\boldsymbol{G}\|_{*}\leq\lambda,\|\boldsymbol{G}\|_{\infty}\leq\gamma\\}\
.$ (7)

We estimate $\boldsymbol{G}^{\star}$ by solving the optimization

$\displaystyle\min_{\boldsymbol{G}\in{\cal
G}_{\lambda,\gamma}}\widehat{R}_{\cal S}(\boldsymbol{G})\ .$ (8)

Since $\boldsymbol{G}^{\star}$ is positive semidefinite, we expect the
diagonal entries of $\boldsymbol{G}^{\star}$ to bound the off-diagonal
entries. So an infinity norm constraint on the diagonal guarantees that the
points $\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{n}$ corresponding to
$\boldsymbol{G}^{\star}$ live inside a bounded $\ell_{2}$ ball. The
$\ell_{\infty}$ constraint in (7) plays two roles: 1) if our loss function is
Lipschitz, large magnitude values of
$\langle\boldsymbol{L}_{t},\boldsymbol{G}\rangle$ can lead to large deviations
of $\widehat{R}_{\cal S}(\boldsymbol{G})$ from $R(\boldsymbol{G})$; bounding
$||\boldsymbol{G}||_{\infty}$ bounds
$|\langle\boldsymbol{L}_{t},\boldsymbol{G}\rangle|$. 2) Later we will define
$\ell$ in terms of the link function $f$ and as the magnitude of
$\langle\boldsymbol{L}_{t},\boldsymbol{G}\rangle$ increases the magnitude of
the derivative of the link function $f$ typically becomes very small, making
it difficult to “invert”; bounding $||\boldsymbol{G}||_{\infty}$ tends to keep
$\langle\boldsymbol{L}_{t},\boldsymbol{G}\rangle$ within an invertible regime
of $f$.

######  Theorem 1.

Fix $\lambda,\gamma$ and assume $\boldsymbol{G}^{\star}\in{\cal
G}_{\lambda,\gamma}$. Let $\widehat{\boldsymbol{G}}$ be a solution to the
program (4). If the loss function $\ell(\cdot)$ is $L$-Lipschitz (or
$|\sup_{y}\ell(y)|\leq L\max\\{1,12\gamma\\}$) then with probability at least
$1-\delta$,

$R(\widehat{\boldsymbol{G}})-R(\boldsymbol{G}^{\star})\leq\frac{4L\lambda}{|{\cal
S}|}\left(\sqrt{\frac{18|{\cal S}|\log(n)}{n}}+\frac{\sqrt{3}}{3}\log
n\right)+L\gamma\sqrt{\frac{288\log{{2}/{\delta}}}{|{\cal S}|}}$

###### Proof.

The proof follows from standard statistical learning theory techniques, see
for instance [13]. By the bounded difference inequality, with probability
$1-\delta$

$\displaystyle R(\widehat{\boldsymbol{G}})-R(\boldsymbol{G}^{\star})$
$\displaystyle=R(\widehat{\boldsymbol{G}})-\widehat{R}_{\cal
S}(\widehat{\boldsymbol{G}})+\widehat{R}_{\cal
S}(\widehat{\boldsymbol{G}})-\widehat{R}_{\cal
S}(\boldsymbol{G}^{\star})+\widehat{R}_{\cal
S}(\boldsymbol{G}^{\star})-R(\boldsymbol{G}^{\star})$ $\displaystyle\leq
2\sup_{\boldsymbol{G}\in{\cal G}_{\lambda,\gamma}}|\widehat{R}_{\cal
S}(\boldsymbol{G})-R(\boldsymbol{G})|\leq
2\mathbb{E}[\sup_{\boldsymbol{G}\in{\cal
G}_{\lambda,\gamma}}|\widehat{R}_{\cal
S}(\boldsymbol{G})-R(\boldsymbol{G})|]+\sqrt{\frac{2B^{2}\log{{2}/{\delta}}}{|S|}}$

where $\sup_{\boldsymbol{G}\in{\cal
G}_{\lambda,\gamma}}\ell(y_{t}\langle\boldsymbol{L}_{t},\boldsymbol{G}\rangle)-\ell(y_{t^{\prime}}\langle\boldsymbol{L}_{t^{\prime}},\boldsymbol{G}\rangle)\leq\sup_{\boldsymbol{G}\in{\cal
G}_{\lambda,\gamma}}L|\langle
y_{t}\boldsymbol{L}_{t}-y_{t^{\prime}}\boldsymbol{L}_{t^{\prime}},\boldsymbol{G}\rangle|\leq
12L\gamma=:B$ using the facts that $\boldsymbol{L}_{t}$ has $6$ non-zeros of
magnitude $1$ and $||\boldsymbol{G}||_{\infty}\leq\gamma$.

Using standard symmetrization and contraction lemmas, we can introduce
Rademacher random variables $\epsilon_{t}\in\\{-1,1\\}$ for all $t\in{\cal S}$
so that

$\mathbb{E}\sup_{\boldsymbol{G}\in{\cal G}_{\lambda,\gamma}}|\widehat{R}_{\cal
S}(\boldsymbol{G})-R(\boldsymbol{G})|\leq\mathbb{E}\sup_{\boldsymbol{G}\in{\cal
G}_{\lambda,\gamma}}\frac{2L}{|{\cal S}|}\left|\sum_{t\in{\cal
S}}\epsilon_{t}\langle\boldsymbol{L}_{t},\boldsymbol{G}\rangle\right|.$

The right hand side is just the Rademacher complexity of ${\cal
G}_{\lambda,\gamma}.$ By definition,

$\\{\boldsymbol{G}:\|\boldsymbol{G}\|_{\ast}\leq\lambda\\}=\lambda\cdot\text{conv}(\\{uu^{T}:|u|=1\\}).$

where $\text{conv}(U)$ is the convex hull of a set $U$. Since the Rademacher
complexity of a set is the same as the Rademacher complexity of it’s closed
convex hull,

$\displaystyle\mathbb{E}\sup_{\boldsymbol{G}\in{\cal
G}_{\lambda,\gamma}}\left|\sum_{t\in{\cal
S}}\epsilon_{t}\langle\boldsymbol{L}_{t},\boldsymbol{G}\rangle\right|$
$\displaystyle\leq\lambda\mathbb{E}\sup_{|u|=1}\left|\sum_{t\in{\cal
S}}\epsilon_{t}\langle\boldsymbol{L}_{t},uu^{T}\rangle\right|=\lambda\mathbb{E}\sup_{|u|=1}\left|u^{T}\left(\sum_{t\in{\cal
S}}\epsilon_{t}\boldsymbol{L}_{t}\right)u\right|$

which we recognize is just $\lambda\mathbb{E}\|\sum_{t\in{\cal
S}}\epsilon_{t}\boldsymbol{L}_{t}\|$. By [14, 6.6.1] we can bound the operator
norm $\|\sum_{t\in S}\epsilon_{t}\boldsymbol{L}_{t}\|$ in terms of the
variance of $\sum_{t\in{\cal S}}\boldsymbol{L}_{t}^{2}$ and the maximal
eigenvalue of $\max_{t}\boldsymbol{L}_{t}.$ These are computed in Lemma 1
given in the supplemental materials. Combining these results gives,

$\frac{2L\lambda}{|{\cal S}|}\mathbb{E}\|\sum_{t\in{\cal
S}}\epsilon_{t}\boldsymbol{L}_{t}\|\leq\frac{2L\lambda}{|{\cal
S}|}\left(\sqrt{\frac{18|{\cal S}|\log(n)}{n}}+\frac{\sqrt{3}}{3}\log
n\right).$

∎

We remark that if $\boldsymbol{G}$ is a rank $d<n$ matrix then

$\|\boldsymbol{G}\|_{\ast}\leq\sqrt{d}\|\boldsymbol{G}\|_{F}\leq\sqrt{d}n\|\boldsymbol{G}\|_{\infty}$

so if $\boldsymbol{G}^{\star}$ is low rank, we really only need a bound on the
infinity norm of our constraint set. Under the assumption that
$\boldsymbol{G}^{\star}$ is rank $d$ with
$||\boldsymbol{G}^{\star}||_{\infty}\leq\gamma$ and we set
$\lambda=\sqrt{d}{n}\gamma$, then Theorem 1 implies that for
$|S|>n\log{n}/161$

$\displaystyle R(\widehat{\boldsymbol{G}})-R(\boldsymbol{G}^{\star})\leq
8L\gamma\sqrt{\frac{18dn\log(n)}{|{\cal
S}|}}+L\gamma\sqrt{\frac{288\log{{2}/{\delta}}}{|{\cal S}|}}$

with probability at least $1-\delta$. The above display says that $|{\cal S}|$
must scale like $dn\log(n)$ which is consistent with known finite sample
bounds [5].

##  3 Maximum Likelihood Estimation

We now turn our attention to recovering metric information about
$\boldsymbol{G}^{\star}$. Let ${\cal S}$ be a collection of triplets sampled
uniformly at random with replacement and let $f:\mathbb{R}\rightarrow(0,1)$ be
a known probability function governing the observations. Any link function $f$
induces a natural loss function $\ell_{f}$, namely, the negative log-
likelihood of a solution $\boldsymbol{G}$ given an observation $y_{t}$ defined
as

$\displaystyle\ell_{f}(y_{t}\langle\boldsymbol{L}_{t},\boldsymbol{G}\rangle)=\mathds{1}_{y_{t}=-1}\log(\tfrac{1}{f(\langle\boldsymbol{L}_{t},\boldsymbol{G}\rangle)})+\mathds{1}_{y_{t}=1}\log(\tfrac{1}{1-f(\langle\boldsymbol{L}_{t},\boldsymbol{G}\rangle)})$

For example, the logistic link function of (1) induces the logistic loss of
(5). Recalling that
$\mathbb{P}(y_{t}=-1)=f(\langle\boldsymbol{L}_{t},\boldsymbol{G}\rangle)$ we
have

$\displaystyle\mathbb{E}[\ell_{f}(y_{t}\langle\boldsymbol{L}_{t},\boldsymbol{G}\rangle)]$
$\displaystyle=f(\langle\boldsymbol{L}_{t},\boldsymbol{G}^{\star}\rangle)\log(\tfrac{1}{f(\langle\boldsymbol{L}_{t},\boldsymbol{G}\rangle)})+(1-f(\langle\boldsymbol{L}_{t},\boldsymbol{G}^{\star}\rangle)\log(\tfrac{1}{1-f(\langle\boldsymbol{L}_{t},\boldsymbol{G}\rangle)})$
$\displaystyle=H(f(\langle\boldsymbol{L}_{t},\boldsymbol{G}^{\star}\rangle))+KL(f(\langle\boldsymbol{L}_{t},\boldsymbol{G}^{\star}\rangle)|f(\langle\boldsymbol{L}_{t},\boldsymbol{G}\rangle))$

where $H(p)=p\log(\tfrac{1}{p})+(1-p)\log(\tfrac{1}{1-p})$ and
$KL(p,q)=p\log(\tfrac{p}{q})+(1-p)\log(\tfrac{1-p}{1-q})$ are the entropy and
KL divergence of Bernoulli RVs with means $p,q$. Recall that
$||\boldsymbol{G}||_{\infty}\leq\gamma$ controls the magnitude of
$\langle\boldsymbol{L}_{t},\boldsymbol{G}\rangle$ so for the moment, assume
this is small. Then by a Taylor series
$f(\langle\boldsymbol{L}_{t},\boldsymbol{G}\rangle)\approx\frac{1}{2}+f^{\prime}(0)\langle\boldsymbol{L}_{t},\boldsymbol{G}\rangle$
using the fact that $f(0)=\frac{1}{2}$, and by another Taylor series we have

$\displaystyle
KL(f(\langle\boldsymbol{L}_{t},\boldsymbol{G}^{\star}\rangle)|f(\langle\boldsymbol{L}_{t},\boldsymbol{G}\rangle))$
$\displaystyle\approx
KL(\tfrac{1}{2}+f^{\prime}(0)\langle\boldsymbol{L}_{t},\boldsymbol{G}^{\star}\rangle|\tfrac{1}{2}+f^{\prime}(0)\langle\boldsymbol{L}_{t},\boldsymbol{G}\rangle)$
$\displaystyle\approx
2f^{\prime}(0)^{2}(\langle\boldsymbol{L}_{t},\boldsymbol{G}^{\star}-\boldsymbol{G}\rangle)^{2}.$

Thus, recalling the definition of $\mathcal{L}(\boldsymbol{G})$ from (4) we
conclude that if
$\widetilde{\boldsymbol{G}}\in\arg\min_{\boldsymbol{G}}R(\boldsymbol{G})$ with
$R(\boldsymbol{G})=\frac{1}{|{\cal T}|}\sum_{t\in{\cal
T}}\mathbb{E}[\ell_{f}(y_{t}\langle\boldsymbol{L}_{t},\boldsymbol{G}\rangle)]$
then one would expect
$\mathcal{L}(\widetilde{\boldsymbol{G}})\approx\mathcal{L}(\boldsymbol{G}^{\star})$.
Moreover, since $\widehat{R}_{\cal S}(\boldsymbol{G})$ is an unbiased
estimator of $R(\boldsymbol{G})$, one expects
$\mathcal{L}(\widehat{\boldsymbol{G}})$ to approximate
$\mathcal{L}(\boldsymbol{G}^{\star})$. The next theorem, combined with Theorem
1, formalizes this observation; its proof is found in the appendix.

######  Theorem 2.

Let $C_{f}=\min_{t\in{\cal T}}\inf_{\boldsymbol{G}\in{\cal
G}_{\lambda,\gamma}}|f^{\prime}\big{(}\langle\boldsymbol{L}_{t},\boldsymbol{G}\rangle\big{)}|$
where $f^{\prime}$ denotes the derivative of $f$. Then for any
$\boldsymbol{G}$

$\displaystyle\frac{2C_{f}^{2}}{|{\cal
T}|}\|\mathcal{L}(\boldsymbol{G})-\mathcal{L}(\boldsymbol{G}^{\star})\|_{F}^{2}\
\leq\ R(\boldsymbol{G})-R(\boldsymbol{G}^{\star})\ .$

Note that if $f$ is the logistic link function of (1) then its straightforward
to show that
$|f^{\prime}\big{(}\langle\boldsymbol{L}_{t},\boldsymbol{G}\rangle\big{)}|\geq\tfrac{1}{4}\exp(-|\langle\boldsymbol{L}_{t},\boldsymbol{G}\rangle|)\geq\tfrac{1}{4}\exp(-6||\boldsymbol{G}||_{\infty})$
for any $t$, $\boldsymbol{G}$ so it suffices to take
$C_{f}=\tfrac{1}{4}\exp(-6\gamma)$.

##  4 Maximum Likelihood Embedding

In this section, let $\widehat{\boldsymbol{G}}$ be the maximum likelihood
estimator; i.e., a solution to the optimization with $L$-Lipschitz log-
likelihood loss function $\ell_{f}$ for a fixed $\lambda,\gamma$. We have
shown that the maximum likelihood estimator allows us to bound
$\|\mathcal{L}(\widehat{\boldsymbol{G}})-\mathcal{L}(\boldsymbol{G}^{\star})\|_{F}^{2}$.
In this section, we discuss how this bound can lead us to recover an
embedding. For the analysis in this section, it will be convenient to work
with distance matrices in addition to Gram matrices. Analogous to the
operators $\boldsymbol{L}_{t}(\boldsymbol{G})$ defined above, we define the
operators $\Delta_{t}$ for $t\in{\cal T}$ satisfying,

$\Delta_{t}(\boldsymbol{D}):=D_{ij}-D_{ik}\equiv L_{t}(\boldsymbol{G})\ .$

We will view the $\Delta_{t}$ as linear operators on the space of symmetric
hollow $n\times n$ matrices $\mathbb{S}^{n}_{h}$, which includes distance
matrices as special cases. As with $\mathcal{L}$, we can arrange all the
$\Delta_{t}$ together, ordering the $t\in{\cal T}$ lexicographically, to
define the $n{n-1\choose{2}}$-dimensional vector

$\Delta(\boldsymbol{D})=[D_{12}-D_{13},\cdots,D_{ij}-D_{ik},\cdots]^{T}.$

We will use the fact that
$\mathcal{L}(\boldsymbol{G})\equiv\Delta(\boldsymbol{D})$ heavily. Because
$\Delta(\boldsymbol{D})$ consists of differences of matrix entries, $\Delta$
has a non-trivial kernel. However, it is easy to see that $\boldsymbol{D}$ can
be recovered given $\Delta(\boldsymbol{D})$ and any one off-diagonal element
of $\boldsymbol{D}$, so the kernel is $1$-dimensional. Also, the kernel is
easy to identify by example. Consider the regular simplex in $d$ dimensions.
The distances between all $n=d+1$ vertices are equal and the distance matrix
can easily be seen to be $\boldsymbol{1}\boldsymbol{1}^{T}-I.$ Thus
$\Delta(\boldsymbol{D})={\bf 0}$ in this case. This gives us the following
simple result.

######  Lemma 2.

Let $\mathbb{S}^{n}_{h}$ denote the space of symmetric hollow matrices, which
includes all distance matrices. For any $\boldsymbol{D}\in\mathbb{S}^{n}_{h}$,
the set of linear functionals $\\{\Delta_{t}(\boldsymbol{D})$, $t\in{\cal
T}\\}$ spans an ${n\choose{2}}-1$ dimensional subspace of
$\mathbb{S}^{n}_{h}$, and the $1$-dimensional kernel is given by the span of
$\boldsymbol{1}\boldsymbol{1}^{T}-\boldsymbol{I}$.

So we see that the operator $\Delta$ is not invertible on
$\mathbb{S}^{n}_{h}$. Define
$\boldsymbol{J}:=\boldsymbol{1}\boldsymbol{1}^{T}-\boldsymbol{I}$. For any
$\boldsymbol{D}$, let $\boldsymbol{C}$, the centered distance matrix, be the
component of $\boldsymbol{D}$ orthogonal to the kernel of $\mathcal{L}$ (i.e.,
$\mbox{tr}(\boldsymbol{C}\boldsymbol{J})=0$). Then we have the orthogonal
decomposition

$\boldsymbol{D}\ =\ \boldsymbol{C}\ +\ \sigma_{D}\,\boldsymbol{J}\ ,$

where
$\sigma_{D}=\mbox{trace}(\boldsymbol{D}\boldsymbol{J})/\|\boldsymbol{J}\|_{F}^{2}$.
Since $\boldsymbol{G}$ is assumed to be centered, the value of $\sigma_{D}$
has a simple interpretation:

$\displaystyle\sigma_{D}=\frac{1}{2{n\choose{2}}}\sum_{1\leq i\leq j\leq
n}D_{ij}=\frac{2}{n-1}\sum_{1\leq i\leq n}\langle
x_{i},x_{i}\rangle=\frac{2\|\boldsymbol{G}\|_{\ast}}{n-1},$ (9)

the average of the squared distances or alternatively a scaled version of the
nuclear norm of $\boldsymbol{G}$. Let $\widehat{\boldsymbol{D}}$ and
$\widehat{\boldsymbol{C}}$ be the corresponding distance and centered distance
matrices.

Now following the notation of sections 2 and 3, assume that there is a true
Gram matrix $\boldsymbol{G}^{\star}$ and a link function $f$ as in section 3,
and assume that we have observed a set of triples ${\cal S}.$ Though $\Delta$
is not invertible on all $\mathbb{S}^{n}_{h}$, it is invertible on the
subspace orthogonal to the kernel, namely $\boldsymbol{J}^{\perp}.$ So if
$\mathcal{L}(\widehat{\boldsymbol{G}})=\Delta(\widehat{\boldsymbol{D}})$ is
close to $\mathcal{L}(\boldsymbol{G}^{\star})$ we expect
$\Delta(\widehat{\boldsymbol{C}})$ to be close to
$\Delta(\boldsymbol{C}^{\star})$. The next theorem quantifies this.

######  Theorem 3.

Consider the setting of Theorems 1 and 2 and let
$\widehat{\boldsymbol{C}},\boldsymbol{C}^{\star}$ be defined as above. Then

$\frac{1}{2{n\choose
2}}\|\widehat{\boldsymbol{C}}-\boldsymbol{C}^{\star}\|_{F}^{2}\
\leq\frac{L\lambda}{4C_{f}^{2}|{\cal S}|}\left(\sqrt{\frac{18|{\cal
S}|\log(n)}{n}}+\frac{\sqrt{3}}{3}\log
n\right)+\frac{L\gamma}{4C_{f}^{2}}\sqrt{\frac{288\log{{2}/{\delta}}}{|{\cal
S}|}}$

###### Proof.

By combining Theorem 2 with the prediction error bounds obtainined in 1 we see
that

$\frac{2C_{f}^{2}}{n\binom{n-1}{2}}\|L(\widehat{\boldsymbol{G}})-L(\boldsymbol{G}^{\star})\|^{2}_{F}\leq\frac{4L\lambda}{|{\cal
S}|}\left(\sqrt{\frac{18|{\cal S}|\log(n)}{n}}+\frac{\sqrt{3}}{3}\log
n\right)+L\gamma\sqrt{\frac{288\log{{2}/{\delta}}}{|{\cal S}|}}.$

Next we employ the following restricted isometry property of $\Delta$ on the
subspace $\boldsymbol{J}^{\perp}$ whose proof is in the supplementary
materials.

######  Lemma 3.

Let $\boldsymbol{D}$ and $\boldsymbol{D}^{\prime}$ be two different distance
matrices of $n$ points in $\mathbb{R}^{d}$ and $\mathbb{R}^{d^{\prime}}$. Let
$\boldsymbol{C}$ and $\boldsymbol{C}^{\prime}$ be the components of
$\boldsymbol{D}$ and $\boldsymbol{D}^{\prime}$ orthogonal to $J$. Then

$n\|\boldsymbol{C}-\boldsymbol{C}^{\prime}\|_{F}^{2}\ \leq\
\|\Delta(\boldsymbol{C})-\Delta(\boldsymbol{C}^{\prime})\|^{2}=\|\Delta(\boldsymbol{D})-\Delta(\boldsymbol{D}^{\prime})\|^{2}\
\leq\ 2(n-1)\|\boldsymbol{C}-\boldsymbol{C}^{\prime}\|_{F}^{2}\ .$

The result then follows. ∎

This implies that by collecting enough samples, we can recover the centered
distance matrix. By applying the discussion following Theorem 1 when
$\boldsymbol{G}^{\star}$ is rank $d$, we can state an upperbound of
$\frac{1}{2{n\choose
2}}\|\widehat{\boldsymbol{C}}-\boldsymbol{C}^{\star}\|_{F}^{2}\ \leq
O\left(\frac{L\gamma}{C_{f}^{2}}\sqrt{\frac{dn\log(n)+\log(1/\delta)}{|{\cal
S}|}}\right)$. However, it is still not clear that this is enough to recover
$\boldsymbol{D}^{\star}$ or $\boldsymbol{G}^{\star}$.

Remarkably, despite this unknown component being in the kernel, we show next
that it can be recovered.

Though $\Delta$ is not invertible on $\mathbb{S}^{n}_{h}$ in general, we can
provide a heuristic argument for why we might still expect it to be invertible
on the (non-linear) space of low rank distance matrices. Since a distance
matrix of $n$ points in $\mathbb{R}^{d}$ is at most rank $d+2$, the space of
all distance matrices has at most $n(d+2)$ degrees of freedom. Now $\Delta$ is
a rank $\binom{n}{2}-1$ operator and since $\binom{n}{2}-1\gg n(d+2)$ for
$n>d+2$, it is not unreasonable to hope that the entries of
$\Delta(\boldsymbol{D})$ provide enough information to parametrize the set of
rank $d+2$ Euclidean distance matrices. In fact as the next theorem will show,
the intuition that $\Delta$ is invertible on the set of low rank distance
matrices is in fact true. Perhaps even more surprisingly, merely knowing the
centered distance matrix $\boldsymbol{C}$ uniquely determines
$\boldsymbol{D}.$

######  Theorem 4.

Let $\boldsymbol{D}$ be a distance matrix of $n$ points in $\mathbb{R}^{d}$,
let $\boldsymbol{C}$ be the component of $\boldsymbol{D}$ orthogonal to the
kernel of $\mathcal{L}$, and let $\lambda_{2}(\boldsymbol{C})$ denote the
second largest eigenvalue of $\boldsymbol{C}$. If $n>d+2$, then

$\boldsymbol{D}\ =\ \boldsymbol{C}\ +\
\lambda_{2}(\boldsymbol{C})\,\boldsymbol{J}\ .$

This shows that $\boldsymbol{D}$ is uniquely determined as a function of
$\boldsymbol{C}$. Therefore, since
$\Delta(\boldsymbol{D})=\Delta(\boldsymbol{C})$ and because $\boldsymbol{C}$
is orthogonal to the kernel of $\Delta$, the distance matrix $\boldsymbol{D}$
can be recovered from $\Delta(\boldsymbol{D})$, even though the linear
operator $\Delta$ is non-invertible.

We now provide a proof of Theorem 4. In preparing this paper for publication
we became aware of an alterntive proof of this theorem [15]. We nevertheless
present our independently derived proof next for completeness.

###### Proof.

To prove Theorem 4 we first state two simple lemmas, which are proved in the
supplementary material.

######  Lemma 4.

Let $\boldsymbol{D}$ be a Euclidean distance matrix on $n$ points. Then
$\boldsymbol{D}$ is negative semidefinite on the subspace

$\boldsymbol{1}^{\perp}:=\\{\boldsymbol{x}\in\mathbb{R}^{n}|\boldsymbol{1}^{T}\boldsymbol{x}=0\\}.$

Furthermore, $\ker(\boldsymbol{D})\subset\boldsymbol{1}^{\perp}$.

######  Lemma 5.

If $\boldsymbol{D}$ is an $n\times n$ distance matrix of rank $r$, then
$\boldsymbol{D}$ has a single positive eigenvalue, $n-r$ eigenvalues equal to
$0$, and $r-1$ negative eigenvalues.

We will use the following notation. For any matrix $\boldsymbol{M}$, let
$\lambda_{i}(\boldsymbol{M})$ denote its $i$th largest eigenvalue. We will
show that for $\sigma>0$ and any $n\times n$ distance matrix $\boldsymbol{D}$
with $n>d+2$,

$\lambda_{2}(\boldsymbol{D}-\sigma\boldsymbol{J})=\sigma\ .$

Since $\boldsymbol{C}=\boldsymbol{D}-\sigma_{D}\boldsymbol{J}$, this proves
the theorem.

Note that
$\lambda_{i}(\boldsymbol{D}-\sigma\boldsymbol{1}\boldsymbol{1}^{T}+\sigma\boldsymbol{I})=\lambda_{i}(\boldsymbol{D}-\sigma\boldsymbol{1}\boldsymbol{1}^{T})+\sigma$,
for $1\leq i\leq n$ and $\sigma$ arbitrary. So it suffices to show that
$\lambda_{2}(\boldsymbol{D}-\sigma\boldsymbol{1}\boldsymbol{1}^{T})=0$.

Let the rank of $\boldsymbol{D}$ be $r$ where $r\leq d+2$ and consider an
eigendecomposition
$\boldsymbol{D}=\boldsymbol{U}\boldsymbol{S}\boldsymbol{U}^{T}$ where
$\boldsymbol{U}$ is unitary. If $\boldsymbol{v}$ is an eigenvector of
$\boldsymbol{D}-\sigma\boldsymbol{1}\boldsymbol{1}^{T}$ with eigenvalue
$\lambda$, then

$\displaystyle\boldsymbol{D}\boldsymbol{v}-\sigma\boldsymbol{1}\boldsymbol{1}^{T}\boldsymbol{v}$
$\displaystyle=\lambda\boldsymbol{v}$
$\displaystyle\Rightarrow\boldsymbol{U}\boldsymbol{S}\boldsymbol{U}^{T}\boldsymbol{v}-\sigma\boldsymbol{1}(\boldsymbol{U}^{T}\boldsymbol{1})^{T}\boldsymbol{U}^{T}\boldsymbol{v}$
$\displaystyle=\lambda\boldsymbol{v}$
$\displaystyle\Rightarrow\boldsymbol{S}\boldsymbol{U}^{T}\boldsymbol{v}-\sigma\boldsymbol{U}^{T}\boldsymbol{1}(\boldsymbol{U}^{T}\boldsymbol{1})^{T}\boldsymbol{U}^{T}\boldsymbol{v}$
$\displaystyle=\lambda\boldsymbol{U}^{T}\boldsymbol{v}.$

So $\boldsymbol{U}^{T}\boldsymbol{v}$ is an eigenvalue of
$\boldsymbol{S}-\sigma\boldsymbol{U}^{T}\boldsymbol{1}(\boldsymbol{U}^{T}\boldsymbol{1})^{T}$
with the same eigenvalue $\lambda.$ Denoting
$\boldsymbol{z}=\boldsymbol{U}^{T}\boldsymbol{1}$, we see that
$\lambda_{i}(\boldsymbol{D}-\sigma\boldsymbol{1}\boldsymbol{1}^{T})=\lambda_{i}(\boldsymbol{S}-\sigma\boldsymbol{z}\boldsymbol{z}^{T})$
for all $1\leq i\leq n$.

By a result on interlaced eigenvalues [16, Cor 4.3.9],

$\lambda_{1}(\boldsymbol{S})\geq\lambda_{1}(\boldsymbol{S}-\sigma\boldsymbol{z}\boldsymbol{z}^{T})\geq\lambda_{2}(\boldsymbol{S})\geq\lambda_{2}(\boldsymbol{S}-\sigma\boldsymbol{z}\boldsymbol{z}^{T})\geq\cdots\geq\lambda_{n}(\boldsymbol{S})\geq\lambda_{n}(\boldsymbol{S}-\sigma\boldsymbol{z}\boldsymbol{z}^{T}).$

From the above inequality and using the fact that
$\lambda_{2}(\boldsymbol{S})=0$ (since $n>d+2$), it is clear that
$\boldsymbol{S}-\sigma\boldsymbol{z}\boldsymbol{z}^{T}$ has at least one
positive eigenvalue. It is also clear that since $\sigma>0$, each eigenvalue
of $\boldsymbol{S}-\sigma\boldsymbol{z}\boldsymbol{z}^{T}$ is bounded above by
an eigenvalue of $\boldsymbol{S}$, so
$\boldsymbol{S}-\sigma\boldsymbol{z}\boldsymbol{z}^{t}$ has at least $r-1$
negative eigenvalues. Hence
$\dim\ker\boldsymbol{S}-\sigma\boldsymbol{z}\boldsymbol{z}^{T}\leq n-r.$

If $\boldsymbol{x}\in\ker\boldsymbol{D}$, then
$\boldsymbol{1}^{T}\boldsymbol{x}=0$ by lemma 4. Thus
$\boldsymbol{x}\in\ker\boldsymbol{D}-\sigma\boldsymbol{1}\boldsymbol{1}^{T}$
and so
$\boldsymbol{U}^{T}\boldsymbol{x}\in\ker\boldsymbol{S}-\sigma\boldsymbol{z}\boldsymbol{z}^{T}.$
This implies that
$\boldsymbol{U}^{T}\ker\boldsymbol{D}\subset\ker\boldsymbol{S}-\sigma\boldsymbol{z}\boldsymbol{z}^{T}$
and $\dim\ker\boldsymbol{S}-\sigma\boldsymbol{z}\boldsymbol{z}^{T}\geq n-r.$
However from the above,
$\dim\ker\boldsymbol{S}-\sigma\boldsymbol{z}\boldsymbol{z}^{T}\leq n-r.$ Hence
we can conclude that
$\lambda_{2}(\boldsymbol{S}-\sigma\boldsymbol{z}\boldsymbol{z}^{T})=0.$ ∎

The previous theorem along with Theorem 3 guarantees that we can recover
$\boldsymbol{G}^{\star}$ as we increase the number of triplets sampled. We
summarize this in our final theorem, which follows directly from Theorems 3
and 4.

######  Theorem 5.

Assume $n>d+2$ and consider the setting of Theorems 1 and 2. As $|{\cal
S}|\rightarrow\infty$, the maximum likelihood estimator

$\widehat{\boldsymbol{G}}=-\frac{1}{2}\boldsymbol{V}(\widehat{\boldsymbol{C}}+\lambda_{2}(\widehat{\boldsymbol{C}})\boldsymbol{J})\boldsymbol{V}$

converges to $\boldsymbol{G}^{\star}$.

##  5 Experimental Study

The section empirically studies the properties of our estimators suggested by
our theory. It is not an attempt to perform an exhaustive empirical evaluation
of different embedding techniques; for that see [17, 4, 6, 3]. In what follows
each of the $n$ points is generated randomly:
$\boldsymbol{x}_{i}\sim\mathcal{N}(0,\tfrac{1}{2d}I_{d})\in\mathbb{R}^{d}$,
$i=1,\dots,n$, motivated by the observation that

$\mathbb{E}[|\langle\boldsymbol{L}_{t},\boldsymbol{G}^{\star}\rangle|]\ =\
\mathbb{E}\big{[}\big{|}\,\|\boldsymbol{x}_{i}-\boldsymbol{x}_{j}\|_{2}^{2}-||\boldsymbol{x}_{i}-\boldsymbol{x}_{k}||_{2}^{2}\,\big{|}\big{]}\
\leq\ \mathbb{E}\big{[}\|\boldsymbol{x}_{i}-\
\boldsymbol{x}_{j}\|_{2}^{2}\big{]}\ =\
2\mathbb{E}\big{[}\|\boldsymbol{x}_{i}\|_{2}^{2}\big{]}\ =\ 1$

for any triplet $t=(i,j,k)$. We perform $36$ trials to see the effect of
different random samples of triplets.

We report the prediction error on a holdout set of $10,000$ triplets and the
error in Frobenius norm of the estimated Gram matrix.

Figure 1: $\boldsymbol{G}^{\star}$ generated with $n=64$ points in $d=2$ and
$d=8$ dimensions on the left and right.

Three algorithms are considered. For each, the domain of the objective
variable $\boldsymbol{G}$ is the space of symmetric positive semi-definite
matrices. None of the methods impose the constraint
$\max_{ij}|G_{ij}|\leq\gamma$ (as done in our theoretical analysis), since
this was used to simplify the analysis and does not have a significant impact
in practice. Rank-d Projected Gradient Descent (PGD) performs gradient descent
on the objective $\widehat{R}_{\cal S}(\boldsymbol{G})=\frac{1}{|S|}\sum_{t\in
S}\log(1+\exp(-y_{t}\langle\boldsymbol{L}_{t},\boldsymbol{G}\rangle))$ with
line search, projecting onto the subspace spanned by the top $d$ eigenvalues
at each step (i.e. setting the bottom $n-d$ eigenvalues to $0$). Nuclear Norm
PGD performs gradient descent on $\widehat{R}_{\cal S}(\boldsymbol{G})$
projecting onto the nuclear norm ball with radius
$\|\boldsymbol{G}^{\star}\|_{*}$, where
$\boldsymbol{G}^{\star}=\boldsymbol{X}^{T}\boldsymbol{X}$ is the Gram matrix
of latent embedding. The nuclear norm projection can have the undesirable
effect of shrinking the non-zero eigenvalues toward the origin. To compensate
for this potential bias, we also employ Nuclear Norm PGD Debiased, which takes
the (biased) output of Nuclear Norm PGD, decomposes it into
$\boldsymbol{U}\boldsymbol{E}\boldsymbol{U}^{T}$ where
$\boldsymbol{U}\in\mathbb{R}^{n\times d}$ are the top $d$ eigenvectors, and
outputs
$\boldsymbol{U}\text{diag}(\widehat{\boldsymbol{s}})\boldsymbol{U}^{T}$ where
$\widehat{s}=\arg\min_{\boldsymbol{s}\in\mathbb{R}^{d}}\widehat{R}_{\cal
S}(\boldsymbol{U}\text{diag}(\boldsymbol{s})\boldsymbol{U}^{T})$. This last
algorithm is motivated by the fact observation that heuristics like minimizing
$\|\cdot\|_{1}$ or $\|\cdot\|_{*}$ are good at identifying the true support or
basis of a signal, but output biased magnitudes [18]. Rank-d PGD and Nuclear
Norm PGD Debiased are novel ordinal embedding algorithms.

Figure 1 presents how the algorithms behave in $n=64$ and $d=2,8$ on the left
and right, respectively. We observe that the unbiased nuclear norm solution
behaves near-identically to the rank-$d$ solution in this case and remark that
this was observed in all of our experiments (see the supplementary materials
for a variety values of $n$, $d$, and scalings of $\boldsymbol{G}^{\star}$). A
popular technique for recovering rank $d$ embeddings is to perform
(stochastic) gradient descent on $\widehat{R}_{\cal
S}(\boldsymbol{U}^{T}\boldsymbol{U})$ with objective variable
$\boldsymbol{U}\in\mathbb{R}^{n\times d}$ taken as the embedding [17, 4, 6].
In all of our experiments this method produced Gram matrices that were nearly
identical to those produced by our Rank-$d$-PGD method, but Rank-$d$-PGD was
an order of magnitude faster in our implementation. Also, in light of our
isometry theorem, we can show that the Hessian of
$\mathbb{E}[\widehat{R}_{\cal S}(\boldsymbol{G})]$ is nearly a scaled
identity, which leads us to hypothesize that a globally optimal linear
convergence result for this non-convex optimization may be possible using the
techniques of [19, 20]. Finally, we note that previous literature has reported
that nuclear norm optimizations like Nuclear Norm PGD tend to produce less
accurate embeddings than those of non-convex methods [4, 6]. We see from the
results that the Nuclear Norm PGD Debiased appears to close the performance
gap between the convex and non-convex solutions.

##  6 Future work

For any fixed set of $n$ points in $\mathbb{R}^{d}$ and randomly selected
distance comparison queries, our results show that the component of
$\boldsymbol{G}^{\star}$ (the Gram matrix associated with the points) in the
span of all possible distance comparisons can be accurately recovered from
$O(dn\log n)$ queries, and we conjecture these bounds to be tight. Moreover,
we proved the existence of an estimator $\widehat{\boldsymbol{G}}$ such that
as the number of queries grows, we have
$\widehat{\boldsymbol{G}}\rightarrow\boldsymbol{G}^{\star}$. A focus of our
ongoing work is characterizing finite sample bounds for the rate at which
$\widehat{\boldsymbol{G}}\rightarrow\boldsymbol{G}^{\star}$. One way of
approaching such a result is showing

$c_{1}\|\boldsymbol{D}-\boldsymbol{D}^{\prime}\|_{F}^{2}\ \leq\
\|\Delta(\boldsymbol{D})-\Delta(\boldsymbol{D}^{\prime})\|^{2}\ \leq\
c_{2}\|\boldsymbol{D}-\boldsymbol{D}^{\prime}\|_{F}^{2}$

for the tightest possible constants $c_{1}$ and $c_{2}$. By inspecting our
proofs, we can provide satisfying values for $c_{1}$ and $c_{2}$, however,
they differ by a factor of $n$ and hence we do not believe these to be tight.
Empirically we observe that if $n\gg d+2$, then the ratio of $c_{1}$ to
$c_{2}$ appears to be independent of $n$.

## References

  * [1] Roger N Shepard.  The analysis of proximities: Multidimensional scaling with an unknown distance function. i.  Psychometrika, 27(2):125–140, 1962.
  * [2] Joseph B Kruskal.  Nonmetric multidimensional scaling: a numerical method.  Psychometrika, 29(2):115–129, 1964.
  * [3] Sameer Agarwal, Josh Wills, Lawrence Cayton, Gert Lanckriet, David J Kriegman, and Serge Belongie.  Generalized non-metric multidimensional scaling.  In International Conference on Artificial Intelligence and Statistics, pages 11–18, 2007.
  * [4] Omer Tamuz, Ce Liu, Ohad Shamir, Adam Kalai, and Serge J Belongie.  Adaptively learning the crowd kernel.  In Proceedings of the 28th International Conference on Machine Learning (ICML-11), pages 673–680, 2011.
  * [5] Kevin G Jamieson and Robert D Nowak.  Low-dimensional embedding using adaptively selected ordinal data.  In Communication, Control, and Computing (Allerton), 2011 49th Annual Allerton Conference on, pages 1077–1084. IEEE, 2011.
  * [6] Laurens Van Der Maaten and Kilian Weinberger.  Stochastic triplet embedding.  In Machine Learning for Signal Processing (MLSP), 2012 IEEE International Workshop on, pages 1–6. IEEE, 2012.
  * [7] Brian McFee and Gert Lanckriet.  Learning multi-modal similarity.  The Journal of Machine Learning Research, 12:491–523, 2011.
  * [8] Matthäus Kleindessner and Ulrike von Luxburg.  Uniqueness of ordinal embedding.  In COLT, pages 40–67, 2014.
  * [9] Yoshikazu Terada and Ulrike V Luxburg.  Local ordinal embedding.  In Proceedings of the 31st International Conference on Machine Learning (ICML-14), pages 847–855, 2014.
  * [10] Ery Arias-Castro.  Some theory for ordinal embedding.  arXiv preprint arXiv:1501.02861, 2015.
  * [11] Mark A Davenport, Yaniv Plan, Ewout van den Berg, and Mary Wootters.  1-bit matrix completion.  Information and Inference, page iau006, 2014.
  * [12] Jon Dattorro.  Convex Optimization & Euclidean Distance Geometry.  Meboo Publishing USA, 2011.
  * [13] Stéphane Boucheron, Olivier Bousquet, and Gábor Lugosi.  Theory of classification: A survey of some recent advances.  ESAIM: probability and statistics, 9:323–375, 2005.
  * [14] Joel A. Tropp.  An introduction to matrix concentration inequalities, 2015.
  * [15] Pablo Tarazaga and Juan E. Gallardo.  Euclidean distance matrices: new characterization and boundary properties.  Linear and Multilinear Algebra, 57(7):651–658, 2009.
  * [16] Roger A Horn and Charles R Johnson.  Matrix analysis.  Cambridge university press, 2012.
  * [17] Kevin G Jamieson, Lalit Jain, Chris Fernandez, Nicholas J Glattard, and Rob Nowak.  Next: A system for real-world development, evaluation, and application of active learning.  In Advances in Neural Information Processing Systems, pages 2638–2646, 2015.
  * [18] Nikhil Rao, Parikshit Shah, and Stephen Wright.  Conditional gradient with enhancement and truncation for atomic norm regularization.  In NIPS workshop on Greedy Algorithms, 2013.
  * [19] Samet Oymak, Benjamin Recht, and Mahdi Soltanolkotabi.  Sharp time–data tradeoffs for linear inverse problems.  arXiv preprint arXiv:1507.04793, 2015.
  * [20] Jie Shen and Ping Li.  A tight bound of hard thresholding.  arXiv preprint arXiv:1605.01656, 2016.

##  7 Supplementary Materials for “Finite Sample Error Bounds for Ordinal
Embedding”

###  7.1 Proof of Lemma 1

######  Lemma 1.

For all $t\in T$,

$\lambda_{1}(\boldsymbol{L}_{t})=\|\boldsymbol{L}_{t}\|=\sqrt{3}$

in addition if $n\geq 3$

$\|\mathbb{E}_{t}[\boldsymbol{L}_{t}^{2}]\|=\frac{6}{n-1}\leq\frac{9}{n}$

###### Proof.

Note that $\boldsymbol{L}_{t}^{3}-3\boldsymbol{L}_{t}=0$ for all $t\in{\cal
T}.$ Thus by the Cayley-Hamilton theorem, $\sqrt{3}$ is the largest eigenvalue
of $\boldsymbol{L}_{t}.$ A computation shows that the submatrix of
$\boldsymbol{L}_{t}^{2}$ corresponding to $i,j,k$ is

$\begin{pmatrix}2&-1&-1\\\ -1&2&-1\\\ -1&-1&2\\\ \end{pmatrix}$

and every other element of $\boldsymbol{L}_{t}^{2}$ is zero. Summing over the
$t\in{\cal T}$ then gives,

$\mathbb{E}[\boldsymbol{L}_{t}^{2}]=\frac{1}{n\binom{n-1}{2}}\sum_{t\in{\cal
T}}\boldsymbol{L}_{t}^{2}=\begin{pmatrix}\frac{6}{n}&\frac{-6}{n(n-1)}&\cdots&\frac{-6}{n(n-1)}\\\
\frac{-6}{n(n-1)}&\frac{6}{n}&\ldots&\frac{-6}{n(n-1)}\\\
\vdots&\ldots&\ldots&\vdots\\\
\frac{-6}{n(n-1)}&\ldots&\frac{-6}{n(n-1)}&\frac{6}{n}\end{pmatrix}$

This matrix can be rewritten as $\frac{6}{n}I-\frac{6}{n(n-1)}\boldsymbol{J}.$
The eigenvalues of $\boldsymbol{J}$ are $-1$ with multiplicity $n-1$ and $n-1$
with multiplicity $1.$ Hence the largest eigenvalue of
$\mathbb{E}[\boldsymbol{L}_{t}^{2}]$ is $\frac{6}{n-1}.$ ∎

###  7.2 Proof of Theorem 2

###### Proof.

For $y,z\in(0,1)$ let $g(z)=z\log{\frac{z}{y}}+(1-z)\log{\frac{1-z}{1-y}}$.
Then $g^{\prime}(z)=\log{\frac{z}{1-z}}-\log{\frac{y}{1-y}}$ and
$g^{\prime\prime}(z)=\frac{1}{z(1-z)}.$ By taking a Taylor series around $y$,

$g(z)\geq\frac{(z-y)^{2}/2}{\sup_{x\in[0,1]}x(1-x)}\geq 2(z-y)^{2}.$

Now applying this to
$z=f(\langle\boldsymbol{L}_{t},\boldsymbol{G}^{\star}\rangle)$ and
$y=f(\langle\boldsymbol{L}_{t},\boldsymbol{G}\rangle)$ gives

$\displaystyle
f(\langle\boldsymbol{L}_{t},\boldsymbol{G}^{\star}\rangle)\log{\tfrac{f(\langle\boldsymbol{L}_{t},\boldsymbol{G}^{\star}\rangle)}{f(\langle\boldsymbol{L}_{t},\boldsymbol{G}\rangle)}}+(1-f(\langle\boldsymbol{L}_{t},\boldsymbol{G}^{\star}\rangle))\log\tfrac{1-f(\langle\boldsymbol{L}_{t},\boldsymbol{G}^{\star}\rangle)}{1-f(\langle\boldsymbol{L}_{t},\boldsymbol{G}\rangle)}$
$\displaystyle\geq
2(f(\langle\boldsymbol{L}_{t},\boldsymbol{G}^{\star}\rangle)-f(\langle\boldsymbol{L}_{t},\boldsymbol{G}\rangle))^{2}$
$\displaystyle\geq
2C_{f}^{2}(\langle\boldsymbol{L}_{t},\boldsymbol{G}^{\star}\rangle-\langle\boldsymbol{L}_{t},\boldsymbol{G}\rangle)^{2}$

where the last line comes from applying Taylor’s theorem to $f$,
$f(x)-f(y)\geq\inf_{z\in[x,y]}f^{\prime}(z)(x-y)$ for any $x,y$. Thus

$\displaystyle R(\boldsymbol{G})-R(\boldsymbol{G}^{\star})$ $\displaystyle=$
$\displaystyle\frac{1}{|{\cal T}|}\sum_{t\in{\cal
T}}f(\langle\boldsymbol{L}_{t},\boldsymbol{G}^{\star}\rangle)\log{\tfrac{f(\langle\boldsymbol{L}_{t},\boldsymbol{G}^{\star}\rangle)}{f(\langle\boldsymbol{L}_{t},\boldsymbol{G}\rangle)}}+(1-f(\langle\boldsymbol{L}_{t},\boldsymbol{G}^{\star}\rangle))\log\tfrac{1-f(\langle\boldsymbol{L}_{t},\boldsymbol{G}^{\star}\rangle)}{1-f(\langle\boldsymbol{L}_{t},\boldsymbol{G}\rangle)}$
$\displaystyle\geq$ $\displaystyle\frac{2C_{f}^{2}}{|{\cal T}|}\sum_{t\in
T}(\langle\boldsymbol{L}_{t},\boldsymbol{G}^{\star}\rangle-\langle\boldsymbol{L}_{t},\boldsymbol{G}\rangle)^{2}$
$\displaystyle=$ $\displaystyle\frac{2C_{f}^{2}}{|{\cal T}|}\sum_{t\in
T}(\langle\boldsymbol{L}_{t},\boldsymbol{G}-\boldsymbol{G}^{\star}\rangle)^{2}=\frac{2C_{f}^{2}}{|{\cal
T}|}\|\mathcal{L}(\boldsymbol{G})-\mathcal{L}(\boldsymbol{G}^{\ast})\|^{2}_{2}.$

∎

###  7.3 Proof of Lemma 3

######  Lemma 3.

Let $\boldsymbol{D}$ and $\boldsymbol{D}^{\prime}$ be two different distance
matrices of $n$ points in $\mathbb{R}^{d}$ and $\mathbb{R}^{d^{\prime}}$
respectively. Let $\boldsymbol{C}$ and $\boldsymbol{C}^{\prime}$ be the
components of $\boldsymbol{D}$ and $\boldsymbol{D}^{\prime}$ orthogonal to
$J$. Then

$n\|\boldsymbol{C}-\boldsymbol{C}^{\prime}\|_{F}^{2}\ \leq\
\|\Delta(\boldsymbol{C})-\Delta(\boldsymbol{C}^{\prime})\|^{2}=\|\Delta(\boldsymbol{D})-\Delta(\boldsymbol{D}^{\prime})\|^{2}\
\leq\ 2(n-1)\|\boldsymbol{C}-\boldsymbol{C}^{\prime}\|_{F}^{2}\ .$

We can view the operator $\Delta$ defined above as acting on the space
$\mathbb{R}^{\binom{n}{2}}$ where each symmetric hollow matrix is identified
with vectorization of it’s upper triangular component. With respect to this
basis $\Delta$ is an $n\binom{n-1}{2}\times\binom{n}{2}$ matrix, which we will
denote by $\Delta$. Since $\boldsymbol{C}$ and $\boldsymbol{C}^{\prime}$ are
orthogonal to the kernel of $\Delta,$ the lemma follows immediately from the
following characterization of the eigenvalues of $\Delta^{T}\Delta.$

######  Lemma 6.

$\Delta^{T}\Delta:\mathbb{S}^{n}_{h}\rightarrow\mathbb{S}^{n}_{h}$ has the
following eigenvalues and eigenspaces,

  * •

Eigenvalue $0$, with a one dimensional eigenspace.

  * •

Eigenvalue $n$, with a $n-1$ dimensional eigenspace.

  * •

Eigenvalue $2(n-1)$, with a $\binom{n}{2}-n$ dimensional eigenspace.

###### Proof.

The rows of $\Delta$ are indexed by triplets $t\in{\cal T}$ and columns
indexed by pairs $i,j$ with $1\leq i<j\leq n$ and vice-versa for $\Delta^{T}.$
The row of $\Delta^{T}$ corresponding to the pair $i,j$ is supported on
columns corresponding to triplets $t=(l,m,n)$ where $m<n$ and $l$ and one of
$m$ or $n$ form the pair $i,j$ or $j,i$. Specifically, letting
$[\Delta^{T}]_{(i,j),t}$ denote the entry of $\Delta^{T}$ corresponding to row
$i,j$ and column $t$,

  * •

if $l=i,m=j$ then $[\Delta^{T}]_{(i,j),t}=1$

  * •

if $l=i,n=j$ then $[\Delta^{T}]_{(i,j),t}=-1$

  * •

if $l=j,m=i$ then $[\Delta^{T}]_{(i,j),t}=1$

  * •

if $l=j,n=i$ then $[\Delta^{T}]_{(i,j),t}=-1$

Using this one can easily check that

$\displaystyle[\Delta^{T}\Delta\boldsymbol{D}]_{i,j}$
$\displaystyle=\sum_{(i,j,k)\in{\cal T}}D_{ij}-D_{ik}-\sum_{(i,k,j)\in{\cal
T}}D_{ik}-D_{ij}+\sum_{(j,i,k)\in{\cal T}}D_{ji}-D_{jk}-\sum_{(j,k,i)\in{\cal
T}}D_{jk}-D_{ji}$ $\displaystyle=2(n-1)D_{ij}-\sum_{n\neq i}D_{in}-\sum_{n\neq
j}D_{jn}.$ (10)

This representation allows us to find the eigenspaces mentioned above very
quickly.

Eigenvalue $0.$ From the above discussion, we know the kernel is generated by
$\boldsymbol{J}=\boldsymbol{1}\boldsymbol{1}^{T}-I$.

Eigenvalue $2(n-1).$ This eigenspace corresponds to all symmetric hollow
matrices such that $\boldsymbol{D}\boldsymbol{1}={\bf 0}$. For such a matrix
each row and column sum is zero and so in particular, the sums in (10) are
both zero. Hence for such a $\boldsymbol{D}$,

$[\Delta^{T}\Delta\boldsymbol{D}]_{i,j}=2(n-1)D_{ij}$

The dimension of this subspace is $\binom{n}{2}-n$, indeed there are
$\binom{n}{2}$ degree of freedom to choose the elements of $\boldsymbol{D}$
and $\boldsymbol{D}\boldsymbol{1}={\bf 0}$ adds $n$ constraints.

Eigenvalue $n.$ This eigenspace corresponds to the span of the matrices
$\boldsymbol{D}^{(i)}$ defined as,

$\boldsymbol{D}^{(i)}=-n(\boldsymbol{e}_{i}\boldsymbol{1}^{T}+\boldsymbol{1}\boldsymbol{e}_{i}^{T}-2\boldsymbol{e}_{i}\boldsymbol{e}_{i}^{T})+2\boldsymbol{J}$

where $\boldsymbol{e}_{i}$ is the standard basis vector with a $1$ in the
$i$th row and $0$ elsewhere. As an example,

$\boldsymbol{D}^{(1)}=\begin{pmatrix}0&-n+2&\cdots&-n+2\\\
\vdots&2&\cdots&2\\\ -n+2&2&\cdots&0\end{pmatrix}.$

If $i,j\neq m$, then $D_{ij}^{(m)}:=[\boldsymbol{D}^{(m)}]_{ij}=2$, and we can
compute the row and column sums

$\sum_{n\neq i}D_{in}^{(m)}=\sum_{n\neq j}D_{jn}^{(m)}=2(n-2)-n+2=n-2.$

This implies that $D_{ij}^{(m)}=n$, and so by (10)

$\displaystyle[\Delta^{T}\Delta\boldsymbol{D}^{(m)}]_{i,j}$
$\displaystyle=2(n-1)\cdot 2-(n-2)-(n-2)\ =\ 2n\ =\ nD_{ij}^{(m)}\ .$

Otherwise, without loss of generality we can assume that $i=m,j\neq m$ in
which case, $[\boldsymbol{D}^{(m)}]_{ij}=-n+2$, the row and columns sums can
be computed as

$\sum_{n\neq i}D_{in}^{(m)}=(n-1)(-n+2)$

and

$\sum_{n\neq j}D_{in}^{(m)}=n-2.$

Putting it all together,

$\displaystyle[\Delta^{T}\Delta\boldsymbol{D}^{(m)}]_{m,j}$
$\displaystyle=2(n-1)\cdot(-n+2)-(n-1)(-n+2)-(n-2)$
$\displaystyle=(n-1)(-n+2)+(-n+2)$ $\displaystyle=n(-n+2)$
$\displaystyle=nD_{m,j}^{(m)}$

and $\Delta^{T}\Delta\boldsymbol{D}=n\boldsymbol{D}.$ Note that the dimension
of $\text{span}{\langle\boldsymbol{D}^{(i)}\rangle}=n-1$ since

$\sum_{m}\boldsymbol{D}^{(m)}=0.$

∎

###  7.4 Proofs of Lemmas 4 and 5

######  Lemma 4.

Let $\boldsymbol{D}$ be a Euclidean distance matrix on $n$ points. Then
$\boldsymbol{D}$ is negative semidefinite on the subspace

$\boldsymbol{1}^{\perp}:=\\{\boldsymbol{x}\in\mathbb{R}^{n}|\boldsymbol{1}^{T}\boldsymbol{x}=0\\}.$

Furthermore, $\ker(\boldsymbol{D})\subset\boldsymbol{1}^{\perp}$.

###### Proof.

The associated Gram matrix
$\boldsymbol{G}=-\frac{1}{2}\boldsymbol{V}\boldsymbol{D}\boldsymbol{V}$ is a
positive semidefinite matrix. For $\boldsymbol{x}\in\boldsymbol{1}^{\perp}$,
$Jx=-x$ so

$x^{T}\left(-\frac{1}{2}\boldsymbol{V}\boldsymbol{D}\boldsymbol{V}\right)x=-\frac{1}{2}\boldsymbol{x}^{T}\boldsymbol{D}\boldsymbol{x}\leq
0$

establishing the first part of the theorem. Now if
$\boldsymbol{x}\in\ker\boldsymbol{D}$,

$\displaystyle
0\leq-\frac{1}{2}\boldsymbol{x}^{T}\boldsymbol{V}\boldsymbol{D}\boldsymbol{V}\boldsymbol{x}=-\frac{1}{2}\boldsymbol{x}^{T}\boldsymbol{1}\boldsymbol{1}^{T}\boldsymbol{D}\boldsymbol{1}\boldsymbol{1}^{T}\boldsymbol{x}=-\frac{1}{2}\boldsymbol{1}^{T}\boldsymbol{D}\boldsymbol{1}(\boldsymbol{1}^{T}\boldsymbol{x})^{2}\leq
0\ ,$

where the last inequality follows from the fact that
$\boldsymbol{1}^{T}\boldsymbol{D}\boldsymbol{1}>0$ since $\boldsymbol{D}$ is
non-negative. Hence $\boldsymbol{1}^{T}\boldsymbol{x}=0$ and
$\ker\boldsymbol{D}\subset\boldsymbol{1}^{\perp}.$ ∎

Let $\lambda_{i}(\boldsymbol{M})$ denote the $i$-th largest eigenvalue of a
matrix $\boldsymbol{M}.$

######  Lemma 5.

If $\boldsymbol{D}$ is an $n\times n$ distance matrix of rank $r$, then

  * •

$\boldsymbol{D}$ has a single positive eigenvalue

  * •

$\boldsymbol{D}$ has $n-r$ zero eigenvalues.

  * •

$\boldsymbol{D}$ has $r-1$ negative eigenvalues.

###### Proof.

From above we know that $r\leq d+2.$ We use the Courant-Fisher theorem [16] .

$\displaystyle\lambda_{1}(\boldsymbol{D})$ $\displaystyle=\max_{\dim
S=1}\min_{0\neq\boldsymbol{x}\in
S}\frac{\boldsymbol{x}^{T}\boldsymbol{D}\boldsymbol{x}}{\boldsymbol{x}^{T}\boldsymbol{x}}$
$\displaystyle\geq\frac{\boldsymbol{1}^{T}\boldsymbol{D}\boldsymbol{1}}{\boldsymbol{1}^{T}\boldsymbol{1}}>0.$

So we see the largest eigenvalue of $\boldsymbol{D}$ is necessarily positive.
Now for $2\leq k\leq n$,

$\displaystyle\lambda_{k}(\boldsymbol{D})$ $\displaystyle=\min_{\dim
S=k}\max_{0\neq\boldsymbol{x}\in
S}\frac{\boldsymbol{x}^{T}\boldsymbol{D}\boldsymbol{x}}{\boldsymbol{x}^{T}\boldsymbol{x}}$
$\displaystyle\leq\min_{U\subset 1^{\perp},\dim
U=k}\max_{0\neq\boldsymbol{x}\in
U}\frac{\boldsymbol{x}^{T}\boldsymbol{D}\boldsymbol{x}}{\boldsymbol{x}^{T}\boldsymbol{x}}$
$\displaystyle\leq 0,$

where the last step follows from the negative definiteness of $\boldsymbol{D}$
on $\boldsymbol{1}^{\perp}$. ∎

##  8 Additional Empirical Results

Figure 2: Varying dimension $n=64$, $d=\\{1,2,4,8\\}$ from top to bottom.

Figure 3: Varying Noise $n=64$, $d=2$, $\alpha M$ for
$\alpha=\\{2,1,\tfrac{1}{2},\tfrac{1}{4}\\}$ from top to bottom.

Figure 4: Varying $\\#$ items $n=\\{16,32,64,128\\}$, $d=2$ from top to
bottom.


# Complementarities in childcare allocation under priorities

Ata Atay and Antonio Romero-Medina

###### Abstract.

We investigate the allocation of children to childcare facilities and propose
solutions to overcome limitations in the current allocation mechanism. We
introduce a natural preference domain and a priority structure that address
these setbacks, aiming to enhance the allocation process. To achieve this, we
present an adaptation of the Deferred Acceptance mechanism to our problem,
which ensures strategy-proofness within our preference domain and yields the
student-optimal stable matching. Finally, we provide a maximal domain for the
existence of stable matchings using the properties that define our natural
preference domain. Our results have practical implications for allocating
indivisible bundles with complementarities.

Ata Atay is a Serra Húnter Fellow (Professor Lector Serra Húnter). Ata Atay
gratefully acknowledges the financial support by the Spanish Ministerio de
Ciencia e Innovación through grant
PID2020-113110GB-100/AEI/10.13039/501100011033, by the Generalitat de
Catalunya through grant 2021SGR00306, and by the University of Barcelona
through grant AS017672. Antonio Romero-Medina acknowledges the financial
support by Spanish Ministerio de Ciencia e Innovación through grant AEI
PID2020-118022GB-I0/AEI/10.13039/501100011033, and Comunidad de Madrid, Grants
EPUC3M11 (V PRICIT) and H2019/HUM-589. We thank José Alcalde, Antonio
Miralles, Jordi Massó, and Matteo Triossi.
Date:
Atay: Department of Mathematical Economics, Finance and Actuarial Sciences,
and Barcelona Economic Analysis Team (BEAT), University of Barcelona, Spain.
E-mail<EMAIL_ADDRESS>
Romero-Medina: Department of Economics, UC3M, Spain. E-mail:
<EMAIL_ADDRESS>
Keywords: childcare allocation $\cdot$ complementarities $\cdot$ market design
$\cdot$ stability $\cdot$ strategy-proofness

JEL Classification: C78 $\cdot$ D47 $\cdot$ D61 $\cdot$ D63 $\cdot$ I21

_”Childcare is a textbook example of a broken market.”_ 111Remarks by
Secretary of the Treasury Janet L. Yellen on Shortages in the Child Care
System (The U.S. Department of Treasury, 2021) reported in The Atlantic ”The
Case for Public Child Care” on January 5, 2023,
https://www.theatlantic.com/family/archive/2023/01/america-public-child-care-
programs/672637/. Accessed on: February 6, 2023.

##  1\. Introduction

Childcare facilities provide parents an alternative to home care and
facilitate children’s cognitive skills development. In many countries, local
governments offer and manage childcare services publicly. Still, these
centralized systems are often met with dissatisfaction and can be a
contentious political issue (see, for instance, Kamada and Kojima, 2020). Our
motivation is the childcare allocation of the Community of Madrid (one of the
17 autonomous communities in Spain), which reflects the main features of
childcare allocation procedures in Spain.

Childcare is not mandatory in Spain, and the scarcity of available slots is
well-documented. For instance, a survey conducted by the National Institute of
Statistics in 2010 revealed that many mothers were compelled to quit their
jobs or reduce their working hours due to inadequate childcare options. In the
Community of Madrid, the enrollment rate in the academic year 2020-2021 was
18.3 % for children under one year, 49.9 % for children under two years, and
66.6 % for children under three years. 222Source: Datos y Cifras de la
Educación 2020-2021. http://www.madrid.org/bvirtual/BVCM050236.pdf. Accessed
on May 27, 2022. The situation is not unique to Madrid. In France, public
childcare slots frequently experience shortages, particularly in public crèche
facilities catering to children under three years of age (OECD, 2020).

Parents tend to prefer enrolling their children in childcare at a later stage
(Meil et al., 2018, 2020). However, they have incentives to secure a childcare
slot as early as possible.333 Evidence of this behavior is frequent; we can
find it in conversations with parents and the press. For example, _“Only 11%
of applicants for slots in municipal schools have been admitted. More than
1000 children have been left without a slot at the schools in the Community of
Madrid.”_ http://fuencarralelpardo.com/2021/09/10/3-600-ninos-sin-plaza-en-
las-escuelas-infantiles-publicas-de-fuencarral-el-pardo/. Accessed on December
11, 2021. There is a consensus among parents that: _“If you want your child to
enter a public childcare that you like, try to sign him/her up before (s)he is
born.”_ 444https://www.elconfidencial.com/espana/2017-05-28/educacion-
temprana-acceso-guarderia-publica-lista-espera_1389553/. Accessed on December
11, 2021. This is because securing a childcare slot grants absolute priority
for enrollment in subsequent years, and the earlier parents apply, the higher
their chances of obtaining one.

When students gain admission to the first year at a childcare facility, they
acquire two objects: a slot for the current year and the highest priority
claim for a slot in the following year. Typically, the preference for these
two objects exhibits a strong positive correlation. In such cases, the
allocation process remains unaffected by distortions. However, parents often
demand more childcare slots than necessary for strategic reasons. Even if they
do not intend to enroll their child in the first year, participating in the
first-year allocation increases the likelihood of securing a slot for the
subsequent year. The presence of a limited number of strategic applicants,
combined with resource scarcity, can result in significant efficiency losses.

This paper examines the distortion caused by history-dependent priorities in
the context of childcare allocation. Following the minimalist market design
approach of Sönmez (2023), we aim to identify the aspects the current
institution design fails to satisfy and provide alternatives that better
fulfill the key objectives. We adopt a two-period allocation process555We
focus on a two-period allocation for simplicity, but our results can be
extended to an arbitrary number of periods, as students retain priority at a
school as long as they remain enrolled. in which slots for the first period
and priorities for the second period are allocated separately. We demonstrate
that eliminating inter-temporal linkage can prevent efficiency loss as agents
cannot manipulate their preferences to enhance their chances of securing a
second-period allocation.

Following Klaus and Klijn (2005) and Klaus et al. (2009), we expand
individuals’ preferences to include choices regarding childcare facilities
during this period and priorities for the subsequent year. We assume that
preferences for schools remain constant across both periods. Overcoming the
challenge of allowing agents to exhibit strong intertemporal complementarities
in their preferences over school slots while breaking the intertemporal
allocation linkage, we enable agents to report strong complementarities
between this year’s school slots and next year’s priority within the same
childcare facility. This property is referred to as the willingness-to-remain
property.

We adapt the student-proposing deferred acceptance ($SPDA$) of Gale and
Shapley (1962) to our problem. We show that the adapted $SPDA$ ($aSPDA$)
mechanism not only returns a stable matching within our preference domain
(Theorem 1) but also remains strategy-proof for students (Theorem 2). Finally,
we show that our preference domain is a maximal domain for the existence of
stable matchings (Proposition 1).

Our findings contribute to the literature on childcare allocation problems in
three significant ways: Firstly, our model differentiates between allocation
and priority as distinct entities, capturing the dynamic nature of the agents’
decision problem. Secondly, students are assigned in cohorts, and our expanded
preference domain accommodates complementarities. Thus, our model is not
encompassed by the many-to-many or matching with couples frameworks. Thirdly,
we propose a stable and strategy-proof mechanism within the extended
preferences domain and priority structure.

###  1.1. Related literature

The childcare allocation problem is dynamic, as children admitted to a
childcare facility retain their slots until they start kindergarten. Unlike
other countries, in Spain, childcare admission follows a cohort system similar
to the school admission problem (see Abdulkadiroğlu and Sönmez, 2003).
Students within a cohort interact in the successive admission process.
However, in the childcare admission process, unlike the school admission
problem, parents determine when each child starts attending childcare. The
closest paper to ours is Kennes et al. (2014), which examines the allocation
of children to public childcare facilities in Denmark. In their setting,
admissions occur monthly, and children’s priority depends on their age.

In contrast, our setting involves yearly cohorts, with no competition among
children of different cohorts. While Kennes et al. (2019) studies the
strategic behavior in a dynamic deferred acceptance (DA) mechanism under
priority structures in Denmark, their model differs from ours as in Kennes et
al. (2019), children of different ages compete for available slots. Similarly,
Kadam and Kotowski (2018) explores a dynamic matching model where agents
interact over time, focusing on agents with preferences on both sides of the
market. In contrast, in our model, schools are endowed with priorities.
Furthermore, the properties introduced to guarantee the stability of matchings
differ from ours. Other related studies include Doval (2022), which defines
dynamic stability in environments where not all agents can be matched
simultaneously and matchings are irreversible; Bloch and Cantala (2013), which
examines the long-run properties of assignment rules in a dynamic matching
problem; Abdulkadiroğlu and Loertscher (2007), which explores a dynamic house
allocation problem with a common set of agents across all periods; Kurino
(2014), which investigates the centralized housing allocation problem with
overlapping generations of agents; Pereyra (2013), which examines teacher
allocation to public schools with seniority-based priorities and demonstrates
strategy-proofness of the DA mechanism in their context; Feigenbaum et al.
(2020), which studies efficient slot reallocation after school admission
cancellations; and Ünver (2010), which extends centralized matching for kidney
exchanges to dynamically evolving agent pools.

Moreover, our paper contributes to the literature on the existence of stable
matchings with complementarities and peer effects (e.g., Dutta and Massó,
1997; Pycia, 2012; Pycia and Yenmez, 2022). The paper by Sun et al. (2022)
closely aligns with ours in this line of research. They address the childcare
allocation problem with siblings in Japan, resembling the matching with
couples model. They propose an algorithm based on integer programming that
does not theoretically guarantee stable matching, but experimental results
consistently yield stable matchings.

Finally, while our results primarily address the allocation of children to
childcare facilities, they also hold relevance for related problems involving
agents with complementarities for bundled goods (e.g., Budish, 2011; Nguyen et
al., 2016; Nguyen and Vohra, 2023). By studying these applications, we can
further explore the implications of our approach.

The paper is organized as follows: Section 2 introduces the model, Section 3
presents our results, and Section 4 concludes.

##  2\. Model

In our model, there is a finite set of students
$I=\left\\{i_{1},i_{2},\text{$\dots$},i_{n}\right\\}$ and a finite set of
childcare facilities that we call schools
$S=\left\\{s_{1},s_{2},\text{$\dots$},s_{m}\right\\}$. The students interact
over two periods. Each student $i$ can be assigned at most one object at each
period $t\in\left\\{1,2\right\\}$. Each school $s\in S$ admits a maximum
number of students each period $t$. We denote the non-negative integer
capacity at time $t$ by $q_{s}^{t}$. The capacity of school $s\in S$ over the
two periods is denoted by $q_{s}=(q_{s}^{1},q_{s}^{2})$. Let $q=(q^{1},q^{2})$
be the vector of first and second-period quotas for all schools.

Each student $i\in I$ has a strict, transitive, and complete preference
relation $P_{i}$ over the set of schools and the possibility of not attending
any school, denoted by $\emptyset$. If $sP_{i}\emptyset$, then school $s$ is
acceptable to student $i$, if $\emptyset P_{i}s$ then school $s$ is
unacceptable to student $i$. Let $P$ be the profile of preferences over
schools for all students.

Students are interested in the school next period. This temporal dimension of
the problem is usually modeled by offering the student absolute priority to
remain in the same school next period. In this paper, we remove the
entanglement between the school allocation (period one) and the priority for
the next period (period two). In period one, student $i$ acquires (possibly) a
school and an absolute priority for the same school in the subsequent period.
666Student $i$ may acquire only an absolute priority for the second period
without securing a school in the first period. It is important to note that
the allocation of slots for periods 1 and 2 will occur through separate
allocation processes at the beginning of each school year.

We denote as $\succ_{i}^{1}$ the preferences of student $i$ for schools in the
first period and $\succ_{i}^{2}$ the preferences for priority in the second
period. It can be represented by a strict ordering of the elements in
$\mathcal{S}:=\left[\left(S\cup\emptyset\right)\times\left(S\cup\emptyset\right)\right]$,
school-priority pairs, as
$\left(\succ_{i}=(\succ_{i}^{1},\succ_{i}^{2})\right)_{i\in I}$, overall
possible combination of ordered pairs of school-priority. We call extended
preferences to the student preferences over school-priority pairs and denote
it by $\mathcal{P}$. To simplify notation, we denote a generic element of
$\mathcal{S}$ by $\left(\sigma_{i},\sigma_{j}\right)$ where
$\sigma_{i},\sigma_{j}\in S\cup\\{\emptyset\\}$. Let $\succ$ denote all
students’ preferences profile over school-priority pairs.

In the remainder of the paper, we restrict the possible student preferences
over pairs of school-priority to the following type we observe in the
childcare allocation problem in our hands. First, we consider the families who
do not want to send their children to a school in the first year.

######  Definition 1.

Extended preferences of a student $i\in I$ are _priority-only_ if
$P_{i}=\succ_{i}^{2}$ and $\succ_{i}^{1}:\emptyset$.

We consider the presence of complementarities between school (period one) and
priority (period two), and assume that students prefer to attend a school only
if they are allocated a slot for period one and have priority for period two
in the same school. Otherwise, they prefer to remain at home.

######  Definition 2.

Extended preferences of a student $i\in I$ are _willingness-to-remain_ if for
all $s_{p},s_{r}\in S$:
$(i)$ $(s_{p},s_{p})\succ_{i}(s_{p},s_{r})$ for all $s_{p}\neq s_{r}$,
$(ii)$ $(s_{p},s_{p})\succ_{i}(s_{r},s_{r})$ for all
$s_{p}P_{i}s_{r}P_{i}\emptyset$, and
$(iii)$ $(\emptyset,\emptyset)\succ_{i}(s_{p},s_{r})$, for all $s_{p}\neq
s_{r}$.

######  Remark 1.

With a slight abuse of notation, we write $\succ_{i}$ to denote $i$’s
preferences over individual schools and allocations of school-priority pairs
whenever there is no ambiguity.

The union of the extended preferences previously defined is the domain of
preferences where we state our results. We formally define the domain of
reasonably extended preferences in Definition 3.

######  Definition 3.

Let $\mathbf{P}$ denote the domain of reasonably extended preferences. For any
$\succ_{i}\in\mathcal{P}$ and $i\in I$, the preference $\succ_{i}$ satisfies
priority-only or willingness-to-remain.

Each school $s\in S$ has a priority ordering $\pi_{s}$ over students. The
priority ordering of a school $s$, $\pi_{s}=(\pi_{s}^{1},\pi_{s}^{2})$, does
not change between periods, i.e., it is the same to allocate, schools and
priorities, $\pi_{s}^{1}=\pi_{s}^{2}$. Let $\pi$ denote the profile of
priorities of schools over students. We assume that the priorities of each
school over sets of students are responsive to the priorities of individual
students. Let $\pi_{s}$ be the priority ordering of school $s$ over students.
We say that $\pi_{s}$ is a _responsive priority ordering_ for all
$I^{\prime}\subseteq I$ with $|I^{\prime}|<q_{s}$, and $i,i^{\prime}$ in
$I\setminus I^{\prime}$ if it satisfies _(i_)
$I^{\prime}\cup\\{i\\}\pi_{s}I^{\prime}\cup\\{i^{\prime}\\}$ if and only if
$i\pi_{s}i^{\prime}$ and _(ii)_ $I^{\prime}\cup\\{i\\}\pi_{s}I^{\prime}$ if
and only if $i$ is acceptable to school $s$. Given a period $t\in\\{1,2\\}$,
the choice of a school $s\in S$, $Ch_{s}^{t}:2^{I}\rightarrow 2^{I}$, is
induced by its priority ordering $\pi_{s}^{t}$ and quota $q_{s}^{t}$, _i.e.,_
$i\in Ch_{s}^{t}(I)$ if and only if there exists no set of students
$I^{\prime}\subseteq I\setminus\\{i\\}$ such that $|I^{\prime}|=q_{s}^{t}$ and
$i^{\prime}\pi_{s}^{t}i$ for $i^{\prime}\in I^{\prime}$. The tuple
$(I,S,\succ,\pi,q)$ describes a childcare allocation problem.

A _matching_ $\mu=(\mu^{1},\mu^{2})$ is a mapping defined on the set $I\cup S$
such that $(\mu^{1}(i),\mu^{2}(i))=\mu(i)\in S\cup\\{\emptyset\\}\times
S\cup\\{\emptyset\\}$ for every $i\in I$, $(\mu^{1}(s),\mu^{2}(s))=\mu(s)\in
2^{I}\times 2^{I}$ for every $s\in S$, and satisfies

  1. (i)

$i\in\mu^{t}(s)$ if and only if $s=\mu^{t}(i)$ for $t=1,2$,

  2. (ii)

$\mu(i)=(s,s^{\prime})$ if and only $i\in\mu^{1}(s)$ and
$i\in\mu^{2}(s^{\prime})$,

  3. (iii)

$\mu^{t}(i)=\emptyset$ means student $i$ is unassigned under $\mu$ at the
period $t$ and $\mu^{t}(s)=\emptyset$ means that school $s$ is unassigned
under $\mu$ at the period $t$,

  4. (iv)

$\mu(i)=(\emptyset,s)$ if and only if $i\in\mu^{2}(s)$ and
$\mu^{1}(i)=\emptyset$; and $\mu(i)=(s,\emptyset)$ if and only if
$i\in\mu^{1}(s)$ and $\mu^{2}(i)=\emptyset$.

$\mathcal{M}$ denotes the set of all matchings. A matching is _individually
rational_ if for no student $i\in I$, $\emptyset\succ_{i}\mu^{t}(i)$ for any
$t\in\\{1,2\\}$, and for all schools $s\in S$,
$Ch_{s}^{t}(\mu^{t}(s))=\mu^{t}(s)$ for $t=1,2$. For a given matching
$\mu=(\mu^{1},\mu^{2})$, blocking coalitions can be formed in different ways:

  * •

$(i,(s,\mu^{2}(i)))\in I\times S\cup\\{\emptyset\\}$ blocks $\mu$ if
$s\succ_{i}\mu^{1}(i)$, $i\in Ch_{s}^{1}(\mu^{1}(s)\cup\\{i\\})$,

  * •

$(i,(\mu^{1}(i),s))\in I\times S\cup\\{\emptyset\\}$ blocks $\mu$ if
$s\succ_{i}\mu^{2}(i)$, $i\in Ch_{s}^{2}(\mu^{2}(s)\cup\\{i\\})$,

  * •

$(i,(s,s^{\prime}))\in I\times(S\cup\\{\emptyset\\}\times
S\cup\\{\emptyset\\})$ blocks $\mu$ if
$s\succ_{i}\mu^{1}(i),s^{\prime}\succ_{i}\mu^{2}(i)$, and $i\in
Ch_{s}^{1}(\mu^{1}(s)\cup\\{i\\})$, $i\in
Ch_{s^{\prime}}^{2}(\mu^{2}(s^{\prime})\cup\\{i\\})$ with the possibility of
$s=s^{\prime}$.

Given a matching $\mu$, if a student’s assignment at a period does not change
under another matching $\mu^{\prime}$, we abuse the notation and represent the
unchanged assignment under $\mu^{\prime}$ by “–”. For instance, given the
assignment of student $i$ under matchings $\mu$ and $\mu^{\prime}$ be
$\mu(i)=(s,s^{\prime})$ and $\mu^{\prime}(i)=(s,s^{\prime\prime})$. Since
student $i$ is assigned to school $s$ at period one both at $\mu$ and
$\mu^{\prime}$, when no confusion arises, we will write
$\mu^{\prime}(i)=(-,s^{\prime\prime})$.

A matching $\mu$ is _stable_ if any coalition does not block it and is
individually rational. A mechanism $\phi$ is a function that maps preference
profiles to matchings. The matching obtained by mechanism $\phi$ at the
preference profile $\succ$ is denoted by $\phi(\succ)$, where
$\phi_{l}(\succ)$ represents the assignment of agent $l\in I\cup S$. We say
that a mechanism is _strategy-proof_ if there does not exist a preference
profile $\succ$ and an agent $l\in I\cup S$, and a preference profile
$\succ^{\prime}$ of agent $l$ such that
$\phi_{l}(\succ^{\prime}_{l},\succ_{-l})\succ_{l}\phi_{l}(\succ)$.

##  3\. Results

We have extended students’ preferences over schools to allow them to express
the possibility of joint school next period without having to attend school in
the first period. In our domain $\mathbf{P}$ of reasonably extended
preferences we can establish an analogy with the matching with couples model
and treat students with priority-only extended preferences as “single”
applicants. In contrast, a student with willingness-to-remain extended
preferences takes the role of a “couple”. The respective employers will be the
schools in the first or the second period. Notice that a crucial difference
with the matching with couples problem is that the first and second periods
are different objects; a student can not abandon a slot in the second period
for a slot in the first period. Therefore, no substitution is possible among
slots in different periods. Next, we introduce the adapted $SPDA$ for our
domain.
Adapted SPDA (aSPDA).
Step 1. Run $SPDA$ algorithm for the sub-market consisting of students with
extended preferences satisfying priority-only, schools take into account only
such students in their priority lists and only quotas for the second period
$q_{2}$. Let $M$ be the set of student-school pairs tentatively matched to
each other. Let $\mu$ be a matching for the initial problems such that the
pairs in $M$ are matched to each other and unmatched otherwise.

Step 2. Fix a random order over the students whose extended preferences
satisfy willingness-to-remain. Following the fixed order and given matching
$\mu$ defined at the end of Step 1, introduce students individually to the
initial market by running $SPDA$. Each student $i$ applies to her remaining
top choice until either a school accepts her or all schools reject her. If
another student $i^{\prime}$ is evicted from her school, then assign student
$i$ tentatively to this school and $i^{\prime}$ applies to her remaining top
choice until either a school accepts her or all schools reject her. Update the
matching $\mu$ after introducing each student in the order by tentatively
assigning students to schools that accept them or students to become unmatched
following $SPDA$.
$aSPDA$ runs until no rejected students want to apply to further schools.

Note that in Step 2 quotas for the first and the second periods should be
respected. Hence, a student whose extended preference satisfies priority-only
still can evict a student whose extended preference satisfies willingness-to-
remain if she has a higher priority. Moreover, due to the complementarities we
observe, the students with willingness-to-remain are willing to not
participate in the first period unless they can participate in both periods.
Hence, no student can fill a seat at a school without hurting other students,
and the obtained matching is not wasteful.

Example 1 illustrates how $aSPDA$ is executed.

######  Example 1.

Consider a childcare allocation problem $(I,S,\mathcal{P},\pi,q)$ with six
students $I=\\{i_{1},i_{2},i_{3},i_{4},i_{5},i_{6}\\}$, two schools
$S=\\{s_{1},s_{2}\\}$ and both schools have a capacity of one student in both
periods, $q^{1}(s_{1},s_{2})=q^{2}(s_{1},s_{2})=(2,2)$. Their extended
preferences are as follows:

$i_{1}:(s_{1},s_{1}),(s_{2},s_{2})$;

$i_{2}:(s_{1},s_{1}),(s_{2},s_{2})$;

$i_{3}:(s_{2},s_{2}),(s_{1},s_{1})$;

$i_{4}:(s_{2},s_{2}),(s_{1},s_{1})$;

$i_{5}:(\emptyset,s_{2}),(\emptyset,s_{1})$;

$i_{6}:(\emptyset,s_{1}),(\emptyset,s_{2})$.

The priorities of the schools are as follows:

$s_{1}:i_{3},i_{4},i_{1},i_{2},i_{6},i_{5}$;

$s_{2}:i_{6},i_{2},i_{5},i_{3},i_{4},i_{1}$.

Notice that there are four students ($i_{1}$, $i_{2}$, $i_{3}$, $i_{4}$) whose
extended preferences satisfy willingness-to-remain. Then, the $SPDA$ algorithm
is run for two students whose extended preferences are priority-only, and
schools consider these students in their priority order while respecting their
quotas only in the second period. It assigns $i_{6}$ to school $s_{1}$ and
$i_{5}$ to school $s_{2}$ in the second period. Then, the tentative assignment
for this sub-market is
$\\{(i_{5},(\emptyset,s_{2})),(i_{6},(\emptyset,s_{1}))\\}$.

Next, fix, for instance, the order $\rho=(i_{1},i_{4},i_{3},i_{2})$ over
students whose preference satisfies willingness-to-remain. First, student
$i_{1}$ applies to her best choice $(s_{1},s_{1})$ and tentatively assigned.
Second, $i_{4}$ enters and applies to her best choice $(s_{2},s_{2})$ and
tentatively assigned. Third, $i_{3}$ enters to the market and starts a
rejection chain: $i_{3}$ evicts $i_{4}$ from $s_{2}$ as
$i_{3}\pi_{s_{2}}i_{4}$. Then, $i_{4}$ applies to her remaining best choice
$s_{1}$ and evicts $i_{6}$. As a result, $i_{6}$ evicts $i_{3}$ from $s_{2}$
and $i_{1}$ from $s_{1}$. Since $i_{1}$ has the lowest priority among
$i_{5},i_{6}$ at school $s_{2}$, $i_{1}$ becomes unmatched. Finally, $i_{2}$
enters the market and, after being rejected by $s_{1}$, applies to $s_{2}$. As
a consequence, $i_{5}$ is evicted from $s_{2}$. Then, she is rejected by
$s_{1}$ and becomes unmatched. Hence, the final matching is
$\mu=\\{(i_{1},(\emptyset,\emptyset)),(i_{2},(s_{2},s_{2})),(i_{3},(s_{1},s_{1})),(i_{4},(s_{1},s_{1})),(i_{5},(\emptyset,\emptyset)),(i_{6},(\emptyset,s_{2})\\}$.

$s_{1}^{1}$ | $s_{1}^{2}$ | $s_{2}^{1}$ | $s_{2}^{2}$ | $\emptyset$ | $\rho$ | entrant
---|---|---|---|---|---|---
| $i_{6}$ |  | $i_{5}$ |  |  | $i_{5},i_{6}$
$i_{1}$ | $i_{1},i_{6}$ |  | $i_{5}$ |  | $(i_{1},i_{4},i_{3},i_{2})$ | $i_{1}$
$i_{1}$ | $i_{1},i_{6}$ | $i_{4}$ |  $i_{4}$, $i_{5}$ |  | $(i_{1},i_{4},i_{3},i_{2})$ | $i_{4}$
$i_{4}$ | $i_{4}$ | $i_{3}$ |  $i_{3}$, $i_{5}$ |  | $(i_{1},i_{4},i_{3},i_{2})$ | $i_{3}$
$i_{3},i_{4}$ | $i_{3},i_{4}$ | $i_{2}$ |  $i_{2}$, $i_{6}$ | $i_{1},i_{5}$ | $(i_{1},i_{4},i_{3},i_{2})$ | $i_{2}$
Table 1. Execution of the mechanism in Example 1.

Table 1 exhibits the execution of the mechanism for the childcare problem
considered in Example 1. Each row in Table 1 represents a tentative assignment
during the execution of the mechanism.

Note that in this example, considering each period (the possibility of a slot
in period one and the priority for a slot in period two) as a separate market
does not lead to a matching for the initial problem. If we take separate
markets for period one, $SPDA$ will assign $i_{1},i_{2}$ to $s_{1}$ in both
periods and $i_{3},i_{4}$ to $s_{2}$ in the first period, while $i_{3},i_{5}$
to $s_{2}$ in the second period. Since $i_{5}$ and $i_{3}$ have higher
priority at $s_{2}$ than $i_{4}$, the matching
$\mu=\\{(i_{1},(s_{1},s_{1})),(i_{2},(s_{1},s_{1})),(i_{3},(s_{2},s_{2})),(i_{4},(\emptyset,\emptyset)),(i_{5},(\emptyset,s_{2})),(i_{6},(\emptyset,\emptyset))\\}$
can be considered as a candidate. Nonetheless, it is not a stable matching for
the initial problem. Hence, if we apply $SPDA$ at each period separately while
respecting the priorities and the quotas, constructing a matching for the
initial problem from the matchings as above may lead to an unstable matching.
Meanwhile, $aSPDA$ does not exhibit this issue.

First, we show that in the domain of reasonably extended preferences
$\mathbf{P}$, there exists a stable matching.

######  Theorem 1.

Given a childcare allocation problem $(I,S,\mathcal{P},\pi,q)$ in the domain
of reasonably extended preferences $\mathbf{P}$, there exists a stable
matching.

###### Proof.

Take the matching $\mu$, which results from $aSPDA$. The matching $\mu$ is
individually rational since no student proposes to an unacceptable school.
Next, we show no pair of $i\in I$ and $s\in S$ blocks $\mu$. Suppose, on the
contrary, there exists such a pair of school $s$ and student $i$.

First, suppose that $i$ never proposes to school $s$. Then student $i$ cannot
be unmatched if school $s$ is acceptable for her. Otherwise, the algorithm
would not end. Under the assumption that $i$ and $s$ blocks matching $\mu$,
$s$ must be acceptable. Hence, $i$ has been matched to another school
$s^{\prime}$ during the $aSPDA$ such that $s^{\prime}\mathcal{P}_{i}s$. It
contradicts the assumption that $i$ and $s$ blocks $\mu$.

Second, suppose that $i$ proposed to school $s$ during $aSPDA$. Then, $i$ must
have been rejected by $s$. Thus, all students tentatively assigned to school
$s$ at this round have higher priority than student $i$. Hence, $i$ and $s$
cannot block the matching $\mu$.

In the meantime, a rejection chain might be started since we introduce
students with willingness-to-remain in a fixed order. We need to show that
there is no rejection cycle. In this case, students who have been rejected
apply to their remaining best choice, which may lead to new rejections
(including of tentatively matched students at a school). Following $aSPDA$,
agents in the rejection chains apply to their best-remaining school until no
rejected agents want to apply for a seat at a school. Since schools have
capacity constraints and students apply to their remaining best choice in the
order of their preferences, any rejection chain is finite. Hence, there is no
rejection cycle. ∎

Next, we show that, in the domain $\mathbf{P}$, it is a dominant strategy for
all students to submit their preferences truthfully.

######  Theorem 2.

Given a childcare allocation problem $(I,S,\mathcal{P},\pi,q)$ in the domain
of reasonably extended preferences $\mathbf{P}$, the $aSPDA$ mechanism is
strategy-proof for students.

###### Proof.

First, notice that a student cannot be better off by misreporting willingness-
to-remain instead of priority-only, and vice versa. Next, suppose otherwise;
i.e. there is an extended preference profile $\mathcal{P}^{\prime}$ such that
$\mathcal{P}^{\prime}_{i}\neq\mathcal{P}_{i}$ for a student $i\in I$ and
$\mathcal{P}^{\prime}_{j}=\mathcal{P}_{j}$ for all other students $j\in
I\setminus\\{i\\}$, the matching $\mu^{\prime}$ is the matching obtained from
$aSPDA$ from the profile $\mathcal{P}^{\prime}$ and $\mu$ is the matching
obtained from $aSPDA$ from the profile $\mathcal{P}$. Then,
$\mu^{\prime}(i)\succ_{i}\mu(i)$. Let $\hat{P_{i}}=(s_{1},\ldots,s_{i-1})$ be
the sequence of schools that student $i$ applies under her true preferences
until she is accepted by the school $\mu(i)$. Then, student $i$ is rejected by
$s_{i-1}$ before accepted by $\mu(i)$. Let also
$\hat{\mathcal{P}^{\prime}_{i}}$ be a sequence of schools such that student
$i$ applies when she misrepresents her true preferences. For
$\hat{\mathcal{P}^{\prime}_{i}}$, we consider two possible cases.

First, suppose that $\mu^{\prime}(i)$ is the least preferred school in
$\hat{\mathcal{P}^{\prime}_{i}}$ based on her true preferences. By
construction of $\mathcal{P}^{\prime}_{i}$, that is the untruthful preference
profile of student $i$, school $\mu^{\prime}(i)$ is ranked higher than
$\mu(i)$. Then, all schools in the sequence $\hat{\mathcal{P}^{\prime}_{i}}$
also appears in the sequence $\hat{\mathcal{P}_{i}}$ under her true
preferences $\mathcal{P}_{i}$. Thus, the Scenario Lemma of Dubins and Freedman
(1981) applies and leads to a contradiction.

Second, suppose that there exists a school $s\in S$ under her true preferences
$\mathcal{P}_{i}$ such that she prefers less than $\mu^{\prime}(i)$, i.e.
$\mu^{\prime}(i)\succ_{i}s$. Then, we can construct another sequence
$\hat{\mathcal{P}^{\prime\prime}_{i}}$ of schools by removing from
$\hat{\mathcal{P}^{\prime}_{i}}$ all the schools that are less desired than
$\mu^{\prime}(i)$ under her true preferences. Then, if student $i$ is assigned
to school $\mu^{\prime}(i)$ following $\hat{\mathcal{P}^{\prime\prime}_{i}}$,
as it is a smaller sequence than $\hat{\mathcal{P}^{\prime}_{i}}$, the
Scenario Lemma of Dubins and Freedman (1981) applies as in the first case and
leads to a contradiction. ∎

###  3.1. Maximal domain

This subsection presents a maximal domain of preferences with the relevant
property. In a childcare allocation problem, if at least one student’s
preferences do not satisfy willingness-to-remain, we can construct preferences
for other students satisfying this property such that no stable matching
exists.

######  Proposition 1.

The domain of reasonably extended preferences $\mathbf{P}$ is a maximal domain
for the existence of stable matchings.

###### Proof.

We prove the proposition by constructing a counterexample where dropping
willingness-to-remain property does not have a stable matching.

Consider a childcare allocation problem with three students
$I=\\{i_{1},i_{2},i_{3}\\}$, two schools $S=\\{s_{1},s_{2}\\}$ and the
capacities of schools are $q^{1}(s_{1},s_{2})=q^{2}(s_{1},s_{2})=(1,2)$. The
preferences of the students are as follows:

$i_{1}:(s_{1},s_{2}),(s_{2},s_{2})$,

$i_{2}:(s_{1},s_{1}),(s_{2},s_{2})$,

$i_{3}:(s_{2},s_{2})$.

The priorities of the schools are as follows:

$s_{1}:i_{1},i_{2}$,

$s_{2}:i_{2},i_{3},i_{1}$.

Notice that the (extended) preferences of student $i_{1}$ fail to satisfy
willingness-to-remain property since
$(s_{1},s_{2})\succ_{i_{1}}(s_{2},s_{2})$.

We see that for each individually rational matching, there exists some
blocking coalitions:

  * •

$\mu=\Big{\\{}\Big{(}i_{1},(s_{1},s_{2})\Big{)},\Big{(}i_{2},(s_{2},s_{2})\Big{)}\Big{\\}}$
is blocked by $\Big{(}i_{3},(s_{2},s_{2})\Big{)}$ with
$s_{2}\succ_{i_{3}}^{1}\emptyset$, $s_{2}\succ_{i_{3}}^{2}\emptyset$, and
$i_{3}\pi_{s_{2}}^{1}\emptyset$, $i_{3}\pi_{s_{2}}^{2}i_{1}$;

  * •

$\mu=\Big{\\{}\Big{(}i_{1},(s_{1},s_{2})\Big{)},\Big{(}i_{3},(s_{2},s_{2})\Big{)}\Big{\\}}$
is blocked by $\Big{(}i_{2},(s_{2},s_{2})\Big{)}$ with
$s_{2}\succ_{i_{2}}^{1}\emptyset$, $s_{2}\succ_{i_{2}}^{2}\emptyset$, and
$i_{2}\pi_{s_{2}}^{1}\emptyset$, $i_{2}\pi_{s_{2}}^{2}i_{1};$

  * •

$\mu=\Big{\\{}\Big{(}i_{1},(s_{2},s_{2})\Big{)},\Big{(}i_{2},(s_{1},s_{1})\Big{)}\Big{\\}}$
is blocked by $\Big{(}i_{3},(s_{2},s_{2})\Big{)}$ with
$s_{2}\succ_{i_{3}}^{1}\emptyset$, $s_{2}\succ_{i_{3}}^{2}\emptyset$, and
$i_{3}\pi_{s_{2}}\emptyset$;

  * •

$\mu=\Big{\\{}\Big{(}i_{1},(s_{2},s_{2})\Big{)},\Big{(}i_{2},(s_{1},s_{1})\Big{)},\Big{(}i_{3},(s_{2},s_{2})\Big{)}\Big{\\}}$
is blocked by $\Big{(}i_{1},(s_{1},-)\Big{)}$ with
$s_{1}\succ_{i_{1}}^{1}\emptyset$, $s_{2}=_{i_{1}}^{2}s_{2}$ and
$i_{1}\pi_{s_{1}}^{1}i_{2}$;

  * •

$\mu=\Big{\\{}\Big{(}i_{1},(s_{2},s_{2})\Big{)},\Big{(}i_{2},(s_{2},s_{2})\Big{)}\Big{\\}}$
is blocked by $\Big{(}i_{3},(s_{2},s_{2})\Big{)}$ with
$s_{2}\succ_{i_{3}}^{1}\emptyset$, $s_{2}\succ_{i_{3}}^{2}\emptyset$, and
$i_{3}\pi_{s_{2}}i_{1}$;

  * •

$\mu=\Big{\\{}\Big{(}i_{2},(s_{2},s_{2})\Big{)},\Big{(}i_{3},(s_{2},s_{2})\Big{)}\Big{\\}}$
is blocked by $\Big{(}i_{2},(s_{1},s_{1})\Big{)}$ with
$s_{1}\succ_{i_{2}}s_{2}$ and $i_{2}\pi_{s_{1}}\emptyset$.

Hence, there is no stable matching.∎

##  4\. Concluding remarks

We address the problem of assigning indivisible objects in the presence of
complementarities among agents. Our focus is on the childcare allocation
problem. Families have incentives to apply for childcare facility slots to
secure priority for future allocations, even if they do not intend to utilize
the facility in the initial period. This incentive creates an excess demand
for childcare slots in the first period, leading to a distortion caused by
these strategic considerations.

A similar distortion manifests in the demand for feeder schools. Feeder
schools are a well-known phenomenon in college admissions around the globe.
Abdulkadiroğlu et al. (2006) points out that most schools in Boston fill their
slots according to a priority order such that the first group of students in
the priority of a school consists of students attending a feeder school.
Research by Wolniak and Engberg (2007) examines the feeder legacy of high
schools, demonstrating that students from feeder schools are more likely to
attend specific colleges. Moreover, attending a feeder school can influence
students’ preferences, as evidenced by Niu et al. (2006), who find that
graduates from feeder schools in Texas prefer selective institutions as their
first choice compared to graduates from non-feeder schools.

To tackle the childcare allocation problem, following a minimalist market
design approach (Sönmez, 2023), we define a natural preference domain in which
the $aSPDA$ mechanism consistently yields a stable matching. Additionally, we
establish the strategy-proofness of the $aSPDA$ mechanism for students in this
specific domain. Lastly, we present a counterexample highlighting how the
preference domain satisfying the willingness-to-remain property represents a
maximum domain in which stable matchings can exist.

## References

  * Abdulkadiroğlu and Loertscher (2007) Abdulkadiroğlu, A. and S. Loertscher (2007), “Dynamic house allocations.” _Mimeo_.
  * Abdulkadiroğlu et al. (2006) Abdulkadiroğlu, A., P. A. Pathak, A.E. Roth, and T. Sönmez (2006), “Changing the Boston school choice mechanism.” _NBER Working Paper_ , 11965.
  * Abdulkadiroğlu and Sönmez (2003) Abdulkadiroğlu, A. and T. Sönmez (2003), “School choice: A mechanism design approach.” _American Economic Review_ , 93, 729–747.
  * Bloch and Cantala (2013) Bloch, F. and D. Cantala (2013), “Markovian assignment rules.” _Social Choice and Welfare_ , 40, 1–25.
  * Budish (2011) Budish, E. (2011), “The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes.” _Journal of Political Economy_ , 119, 1061–1103.
  * Dirección General de Bilingüismo y Calidad de la Enseñanza (2021) Dirección General de Bilingüismo y Calidad de la Enseñanza (2021), “Datos y Cifras de la educación 2020-2021.” Technical report, Comunidad de Madrid, URL http://www.madrid.org/bvirtual/BVCM050236.pdf. Accessed on May 27, 2022.
  * Doval (2022) Doval, L. (2022), “Dynamically stable matching.” _Theoretical Economics_ , 17, 687–724.
  * Dubins and Freedman (1981) Dubins, L. E. and D. A. Freedman (1981), “Machiavelli and the Gale-Shapley algorithm.” _The American Mathematical Monthly_ , 88, 485–494.
  * Dutta and Massó (1997) Dutta, B. and J. Massó (1997), “Stability of matchings when individuals have preferences over colleagues.” _Journal of Economic Theory_ , 75, 464–475.
  * El Confidencial (2017) El Confidencial (2017), “La odisea de encontrar plaza en la guardería pública: “Se solicita antes de que nazcan”.” URL https://www.elconfidencial.com/espana/2017-05-28/educacion-temprana-acceso-guarderia-publica-lista-espera_1389553/. Accessed on December 11, 2021.
  * Feigenbaum et al. (2020) Feigenbaum, I., Y. Kanoria, I. Lo, and J. Sethuraman (2020), “Dynamic matching in school choice: Efficient seat reassignment after late cancellations.” _Management Science_ , 66, 5341–5361.
  * fuencarralelpardo.com (2021) fuencarralelpardo.com (2021), “3.600 niños sin plaza en las escuelas infantiles públicas de Fuencarral-El Pardo.” URL http://fuencarralelpardo.com/2021/09/10/3-600-ninos-sin-plaza-en-las-escuelas-infantiles-publicas-de-fuencarral-el-pardo/. Accessed on December 11, 2021.
  * Gale and Shapley (1962) Gale, D. and L. S. Shapley (1962), “College admissions and the stability of marriage.” _The American Mathematical Monthly_ , 69, 9–15.
  * Kadam and Kotowski (2018) Kadam, S. V. and M. H. Kotowski (2018), “Multiperiod matching.” _International Economic Review_ , 59, 1927–1947.
  * Kamada and Kojima (2020) Kamada, Y. and F. Kojima (2020), “Fair matching under constraints: Theory and applications.” _The Review of Economic Studies_. Forthcoming.
  * Kennes et al. (2014) Kennes, J., D. Monte, and N. Tumennasan (2014), “The day care assignment: A dynamic matching problem.” _American Economic Journal: Microeconomics_ , 6, 362–406.
  * Kennes et al. (2019) Kennes, J., D. Monte, and N. Tumennasan (2019), “Strategic performance of deferred acceptance in dynamic matching problems.” _American Economic Journal: Microeconomics_ , 11, 55–97.
  * Klaus and Klijn (2005) Klaus, B. and F. Klijn (2005), “Stable matchings and preferences of couples.” _Journal of Economic Theory_ , 121, 75–106.
  * Klaus et al. (2009) Klaus, B., F. Klijn, and T. Nakamura (2009), “Corrigendum to “stable matchings and preferences of couples” [J. Econ. Theory 121 (1)(2005) 75–106].” _Journal of Economic Theory_ , 144, 2227–2233.
  * Kurino (2014) Kurino, M. (2014), “House allocation with overlapping generations.” _American Economic Journal: Microeconomics_ , 6, 258–289.
  * Meil et al. (2020) Meil, G., I. Lapuerta, and A. Escobedo (2020), “Spain country note.” In _16th International Review of Leave Policies and Related Research_ (A. Koslowski, S. Blum, I. Dobrotić, G. Kaufman, and P. Moss, eds.), Leave Network.
  * Meil et al. (2018) Meil, G., P. Romero-Balsas, and J. Rogero-García (2018), “Parental leave in Spain: Use, motivations and implications.” _Revista Española de Sociología_ , 27, 27–43.
  * Nguyen et al. (2016) Nguyen, T., A. Peivandi, and R. Vohra (2016), “Assignment problems with complementarities.” _Journal of Economic Theory_ , 165, 209–241.
  * Nguyen and Vohra (2023) Nguyen, T. and R. Vohra (2023), “Complementarities and externalities.” In _Online and Matching-Based Market Design_ (F. Echenique, N. Immorlica, and V. V. Vazirani, eds.), Cambridge University Press.
  * Niu et al. (2006) Niu, S. X., M. Tienda, and K. Cortes (2006), “College selectivity and the Texas top 10% law.” _Economics of Education Review_ , 25, 259–272.
  * OECD (2020) OECD (2020), “Is childcare affordable?” Technical report, Policy Brief on Employment, Labour and Social Affairs, URL http://oe.cd/childcare-brief-2020.
  * Pereyra (2013) Pereyra, J. S. (2013), “A dynamic school choice model.” _Games and Economic Behavior_ , 80, 100–114.
  * Pycia (2012) Pycia, M. (2012), “Stability and preference alignment in matching and coalition formation.” _Econometrica_ , 80, 323–362.
  * Pycia and Yenmez (2022) Pycia, M. and M. B. Yenmez (2022), “Matching with externalities.” _The Review of Economic Studies_. Forthcoming.
  * Sönmez (2023) Sönmez, T. (2023), “Minimalist Market Design: A Framework for Economists with Policy Aspirations.” Mimeo.
  * Sun et al. (2022) Sun, Z., Y. Takenami, D. Moriwaki, Y. Tomita, and M. Yokoo (2022), “Daycare matching in Japan: Transfers and siblings.” _arXiv preprint arXiv:2212.02751_.
  * The U.S. Department of Treasury (2021) The U.S. Department of Treasury (2021), “The economics of child care supply in the united states.” Technical report, The U.S. Department of Treasury, URL https://home.treasury.gov/system/files/136/The-Economics-of-Childcare-Supply-09-14-final.pdf.
  * Ünver (2010) Ünver, M. U. (2010), “Dynamic kidney exchange.” _The Review of Economic Studies_ , 77, 372–414.
  * Wolniak and Engberg (2007) Wolniak, G. C. and M. E. Engberg (2007), “The effects of high school feeder networks on college enrollment.” _The Review of Higher Education_ , 31, 27–53.