# Geometric planted matchings beyond the Gaussian model

Lucas R. Schwengber<EMAIL_ADDRESS>IMPA, Rio de Janeiro, Brazil
Roberto I. Oliveira<EMAIL_ADDRESS>IMPA, Rio de Janeiro, Brazil

(2024)

### Abstract

We consider the problem of recovering an unknown matching between a set of $n$
randomly placed points in $\mathbb{R}^{d}$ and random perturbations of these
points. This can be seen as a model for particle tracking and more generally,
entity resolution. We use matchings in random geometric graphs to derive
minimax lower bounds for this problem that hold under great generality. Using
these results we show that for a broad class of distributions, the order of
the number of mistakes made by an estimator that minimizes the sum of squared
Euclidean distances is minimax optimal when $d$ is fixed and is optimal up to
$n^{o(1)}$ factors when $d=o(\log n)$. In the high-dimensional regime we
consider a setup where both initial positions and perturbations have
independent sub-Gaussian coordinates. In this setup we give sufficient
conditions under which the same estimator makes no mistakes with high
probability. We prove an analogous result for an adapted version of this
estimator that incorporates information on the covariance matrix of the
perturbations.

##  1 Introduction

We study the geometric planted matching model introduced by D. Kunisky and J.
Niles-Weed in [11]. Given $n,d\in\mathbb{N}$, we generate a sequence
$X_{1},\dots,X_{n}$ of independent and identically distributed (i.i.d.) random
positions in $\mathbb{R}^{d}$ and independently a sequence of i.i.d. random
perturbations $Z_{1},\dots,Z_{n}$, from which we derive,

$Y_{i}=X_{\pi^{\star}(i)}+Z_{i},\leavevmode\nobreak\ i\in[n],$ (1.1)

a sequence of perturbed versions of the original points with the label
information hidden by an unknown random permutation
$\pi^{\star}\sim\text{Unif}(S_{n})$. The goal is to recover $\pi^{\star}$
given direct observation of $X_{1},\dots,X_{n}$ and $Y_{1},\dots,Y_{n}$.

We can interpret $\\{X_{1},\dots,X_{n}\\}$ and $\\{Y_{1},\dots,Y_{n}\\}$ as
being snapshots at different times of the positions of $n$ particles
performing some form of random motion in $\mathbb{R}^{d}$. Based on these
snapshots we would like to track each particle’s trajectory. This is a natural
problem that arises in the life sciences [18, 3, 9] in the context of
analyzing single-cell dynamics, and in the physical sciences [12] in problems
involving fluid dynamics. This model also makes sense for growing $d$. For
instance, if we imagine that the $X_{i}$’s are high-dimensional feature
vectors, and the $Y_{i}$’s are noisy versions of the $X_{i}$’s, then
estimating $\pi^{*}$ is a toy model for entity resolution or deduplication
[5].

Under the assumption that $X_{i}\sim\mathcal{N}(0,I_{d})$ and
$Z_{i}\sim\mathcal{N}(0,\sigma^{2}I_{d})$, [11] established sufficient and
necessary conditions on $\sigma^{2}$ for the number of mistakes made by the
maximum likelihood estimator (MLE) to be $0$ or $o(n)$ with high-probability
for different regimes of $d$. Under the same Gaussian model, [24] showed that
some of these conditions are information theoretical optimal. In [6] and [2]
information-theoretical limits were also established under different models
for database matching with Gaussian assumptions. Another line of research,
tracing back to [4], considers the problem of recovering planted matchings in
weighted bipartite graphs without a latent geometric structure. In that case,
more general results are available [13, 17, 8].

In this work we consider the geometric planted matching problem following
(1.1) for broader classes of distributions for $X_{i}$ and $Z_{i}$. In this
more general setting, we obtain a general lower bound on the expected number
of mistakes made by any estimator. Our proof is based on a simple argument
involving matchings in random geometric graphs. The same strategy can also be
used to establish negative results similar to the ones in [11] and [24]. We
showcase some consequences for the regime when $d=\Theta(1)$ and $d=o(\log n)$
providing natural scenarios where it gives optimal results up to constant
factors in the first regime, and up to $n^{o(1)}$ factors in the latter one.

We also obtain results in high-dimensional settings when both the initial
positions and noise vectors have anisotropic sub-Gaussian distributions. This
is motivated by the connection with data deduplication, where non-isotropy
seems natural. Our main finding is that there seems to be natural “effective
dimension” and “effective SNR” parameters that govern the matching problem in
this setting, much like the true dimension determines the error rate for
isotropic Gaussians [11].

###  1.1 Main results

In what follows, an estimator $\hat{\pi}$ is a map that takes as input two
sequences of $n$ points in $\mathbb{R}^{d}$, $X_{1},\dots,X_{n}$ and
$Y_{1},\dots,Y_{n}$, and outputs a permutation $\hat{\pi}\in S_{n}$. We
measure the performance of such estimator $\hat{\pi}$ using the Hamming
distance with respect to the true planted matching $\pi^{\star}$:

$d_{H}\left({\hat{\pi}},{\pi^{\star}}\right)=\sum_{j=1}^{n}\mathbf{1}_{[\hat{\pi}(j)\neq\pi^{\star}(j)]}.$
(1.2)

As in previous works [4, 13, 17, 8, 11, 24] we want to understand the
behaviour of the above quantity and its expectation for large $n$. More
concretely, we would like to establish upper bounds on the expected number of
mistakes made by a certain estimator (positive results), and lower bounds on
the same quantity that hold for some, or for any, estimator (negative
results).

For our positive results, we focus on an estimator that solves:

$\displaystyle\hat{\pi}_{\mathrm{LSS}}$ $\displaystyle=\underset{\pi\in
S_{n}}{\text{arg min}}\sum_{j=1}^{n}\left\|{X_{\pi(j)}-Y_{j}}\right\|_{2}^{2}$
(1.3) $\displaystyle=\underset{\pi\in S_{n}}{\text{arg
max}}\sum_{j=1}^{n}\langle X_{\pi(j)},Y_{j}\rangle.$

Under the Gaussian model from [11] this coincides with the MLE, but it can
also be used in more general settings. Following [6] we will refer to this
estimator as the Least Sum of Squares Estimator (LSS).

This estimator is distribution agnostic and can also be evaluated efficiently
using the Hungarian method [10] since it is an instance of a linear assignment
problem. It appeared in previous theoretical analysis [11, 24, 2, 6] under
Gaussian assumptions and in practical applications [9]. Not directly related
to this work there exists an extensive literature on understanding the
asymptotic behaviour of so-called Euclidean Bipartite Matching Problems [19,
20], which have the same structure as the random optimization problem in
(1.3), but the $Y_{i}$’s are assumed to be an independent copy of the
$X_{i}$’s.

####  1.1.1 Low-dimension

Our first two results are specially informative when $d=o(\log n)$. This
includes the case where $d$ is fixed, which is the natural setting for the
problem of particle tracking when the number of particles being tracked is
very large [4].

######  Model LD.

We generate a model following (1.1) with the assumption that:

  1. (a)

$X_{1},\dots,X_{n}\stackrel{{\scriptstyle\text{iid}}}{{\sim}}\mathcal{P}$
where $\mathcal{P}$ is a probability distribution on $\mathbb{R}^{d}$ such
that:

    1. (i)

$\mathcal{P}(\\{x\in\mathbb{R}^{d};\leavevmode\nobreak\
\left\|{x}\right\|<R_{d}\\})\geq\gamma$ for some norm $\|\,\cdot\,\|$ and
$R_{d},\gamma>0$.

    2. (ii)

$\mathcal{P}$ has a density $f_{\mathcal{P}}$, with respect to Lebesgue
measure in $\mathbb{R}^{d}$, such that:

$\frac{\operatorname*{ess\,sup}\limits_{\left\|{x}\right\|<R_{d}}f_{\mathcal{P}}(x)}{\operatorname*{ess\,inf}\limits_{\left\|{x}\right\|<R_{d}}f_{\mathcal{P}}(x)}\leq
e^{\beta d},$ (1.4)

for some constant $\beta\geq\log(2)$.

  2. (b)

$Z_{1},\dots,Z_{n}=\sigma\tilde{Z}_{1},\dots,\sigma\tilde{Z}_{n}$, where
$\sigma>0$ is the noise level and
$\tilde{Z}_{1},\dots,\tilde{Z}_{n}\stackrel{{\scriptstyle\text{iid}}}{{\sim}}\mathcal{Q}$
are random directions of motion following $\mathcal{Q}$ a distribution in
$\mathbb{R}^{d}$ such that:

$\sup_{\left\|{v}\right\|<R_{d}}\left\|{\mathcal{Q}(v)\otimes\mathcal{Q}(-v)-\mathcal{Q}\otimes\mathcal{Q}}\right\|_{TV}\leq
1-e^{-\beta d},$ (1.5)

where $\mathcal{Q}(v)$ is the law of $\tilde{Z}_{1}+v$, and
$\|\,\cdot\,\|,R_{d},\gamma$ and $\beta$ are the same as in assumption a.

Loosely speaking, assumption (a) says that there is a ball carrying a positive
part of the mass of $\mathcal{P}$ where the density $f_{\mathcal{P}}$ does not
vary too much. Assumption (b) is expected to be satisfied when $\mathcal{Q}$
has a density with a significant overlap with bounded translations of itself.
For instance, these assumptions naturally hold for
$\mathcal{P}=\mathcal{Q}=\mathcal{N}(0,I_{d})$ with
$\|\,\cdot\,\|=\left\|{\,\cdot\,}\right\|_{2}$, $R_{d}=\sqrt{2d}$ and
$\beta,\gamma>0$ which are independent of $d$ and $n$. But they also hold if
we only assume that $\mathcal{P}$ and $\mathcal{Q}$ have bounded continuous
densities (see §2.2 below).

Under the above assumptions, we have following explicit minimax lower bound:

######  Theorem 1.1 (Minimax lower bound (proof in §3.3)).

Under LD, for all $n\geq 3$,

$\inf_{\hat{\pi}}\mathbb{E}\left[d_{H}\left({\hat{\pi}},{\pi^{\star}}\right)\right]\geq\frac{\gamma^{2}}{32}e^{-7\beta
d}\left((n^{2}\sigma^{d})\wedge n\right),$ (1.6)

where the infimum above is taken over all estimators $\hat{\pi}$.

The proof of this result is based on a natural argument that uses matchings in
the random geometric graph
$G(n,r,d,\|\,\cdot\,\|)=G(\\{X_{1},\dots,X_{n}\\},r,d,\|\,\cdot\,\|)$
constructed by joining pairs of initial positions which are within a distance
$r$ of each other with respect to norm $\|\,\cdot\,\|$. As a main step in this
proof we also show the following result of independent interest:

######  Lemma 1.2 (Largest matching size lower bound (proof in §3.2)).

Let $X_{1},\dots,X_{n}\stackrel{{\scriptstyle\text{iid}}}{{\sim}}\mathcal{P}$
and $M_{r}$ be the largest matching in $G(n,r,d,\|\,\cdot\,\|)$ and suppose
$\mathcal{P}$, $\|\,\cdot\,\|,R_{d},\gamma$ and $\beta$ follow assumption a
from LD. Then for all $n\geq 3$ and $r>0$,

$\mathbb{E}\left[|M_{r}|\right]\geq\frac{\gamma^{2}}{16}e^{-6\beta
d}\left(\left(n^{2}\left(\frac{r}{R_{d}}\right)^{d}\right)\wedge n\right).$
(1.7)

Given Lemma 1.2, the idea of the proof of Theorem 1.1 is that a large matching
in $G(n,r,d,\|\,\cdot\,\|)$ implies that a large number of pairs of points
$X_{i}$ and $X_{j}$ are very close to one another. Since points which are
close to each other are hard to distinguish once noise is added, they are
likely to lead to mistakes. This phenomenon is illustrated in Figure 1 for
$\hat{\pi}_{\mathrm{LSS}}$. Following this proof strategy, when $d$ is fixed,
the order $(n^{2}\sigma^{d})\wedge n$ appearing in Theorem 1.1 has a very
natural geometrical interpretation: it is the order of the size of the largest
matching of initial positions within distance $\Theta(\sigma)$.

Figure 1: A small window of a simulation of the performance of
$\hat{\pi}_{\mathrm{LSS}}$ on a sample following (1.1) of total size $n=3000$
with $X_{1}\sim\mathcal{N}(0,I_{d})$,
$Z_{1}\sim\mathcal{N}(0,\sigma^{2}I_{d})$ for two different values of
$\sigma^{2}$. Arrows indicate to which initial position $X_{i}$ a given
$Y_{j}$ was associated by $\hat{\pi}_{\mathrm{LSS}}$. Red arrows indicate that
the estimated match for the given point was incorrect, while grey arrows
indicate that the estimated match was correct. Blue lines between pairs of
initial positions indicate that they are within a distance of
$r=\sqrt{2}\sigma$ of each other. Note that most incorrect matches involve
initial positions that share an edge on
$G(n,r,d,\left\|{\,\cdot\,}\right\|_{2})$. Our strategy to prove our lower
bounds takes inspiration from this observation. The code to generate this
image can be found at https://github.com/Lucas-Schwengber/particle_tracking.

Although to the best of our knowledge understanding matchings in random
geometric graphs has not received direct attention in previous works, Lemma
1.2 is not significantly far from what is already well-known in the
literature. For instance, if $d$, $\mathcal{P}$ and $\mathcal{Q}$ are fixed,
$r\to 0$ and $n^{2}r^{d}\to+\infty$, one can use general results of the
classical monograph by Penrose [15, Propositions 3.2 and 3.3] to count
isolated edges in a random geometric graph, giving a lower bound on the size
of its largest matching which is sharp up to constant factors. For our
purposes, the main advantage of Lemma 1.2 is that it is general, nonasymptotic
and can be made to work in growing dimensions. Moreover, its proof is simple
and constructive.

######  Remark 1.3.

Our approach to establish lower bounds is different from what was done in [11]
where the authors look at matchings in a different random graph, which is
built by adding edges between the endpoints of augmenting $2$-cycles (see
Section B.1 below for a definition). There is a direct connection between the
two approaches, which we outline in Appendix B. In particular, when $d=o(\log
n)$ or $d$ is fixed, our techniques are able to recover the lower bounds from
[11] up to factors of order $n^{o(1)}$, while also working under greater
generality (see Theorem B.1).

######  Remark 1.4.

The proof strategy of our negative results also differs from the one in [24]
where the authors either count augmenting $2$-cycles as in [11] or use
classical tools from information theory. But one can also prove a version of
Theorem 1.1 that gives a lower bound in probability for the performance of any
estimator, thus allowing us to derive negative results that complement and
extend the negative results from [24] (see Corollary B.6 in Appendix B) when
$d$ is fixed or $d=o(\log n)$.

######  Remark 1.5.

We note that, similar to this work, [2] and [6] also established information-
theoretical limits by analyzing the distances between uncorrupted feature
vectors. However their conditions are stated in terms of the minimum distance
between uncorrupted feature vectors.

######  Remark 1.6.

Although the negative results established in this paper concern the case when
$d=o(\log n)$, we believe our strategy can also lead to non-trivial results
when $d=\Omega(\log n)$. In particular, in Appendix C we showcase how they can
be used to partially recover the lower bounds from [11] in the regime where
$d=\Theta(\log n)$.

Our next result shows that the LSS estimator achieves minimax optimal rates in
a slightly more restrictive setting than LD. Specifically, let LD+S be LD with
the additional assumptions that:

  1. (c)

$\left\|{f_{\mathcal{P}}}\right\|_{\infty}\leq e^{\beta d}$, for the same
$\beta$ as in assumption a.

  2. (d)

The distribution of the $\tilde{Z}_{i}$’s satisfy:

$\sup\limits_{\left\|{v}\right\|=1}\left\|{\left\langle{\tilde{Z}_{i}},{v}\right\rangle}\right\|_{\psi_{2}}\leq
K_{Q}\text{ and }\mathbb{E}[\tilde{Z}_{i}]=0.$ (1.8)

Under these additional assumptions, we have the following upper bound on
$\mathbb{E}\left[d_{H}\left({\hat{\pi}_{\mathrm{LSS}}},{\pi^{\star}}\right)\right]$:

######  Theorem 1.7 (LSS error upper bound (proof in §4.1)).

Under LD+S , for all $n\geq 2$,

$\mathbb{E}\left[d_{H}\left({\hat{\pi}_{\mathrm{LSS}}},{\pi^{\star}}\right)\right]\leq(3K^{d}n^{2}\sigma^{d})\wedge
n,$ (1.9)

where
$K=b_{\mathrm{LD}}\left\|{f_{\mathcal{P}}}\right\|_{\infty}^{\frac{2}{d}}K_{\mathcal{Q}}^{2}e^{2\beta}$
for some absolute constant $b_{\mathrm{LD}}>0$.

In Section 2.2 below we show that if $d$ is fixed we can improve our constant
$3K^{d}$ to a constant $\tau_{d,\mathcal{P},\mathcal{Q}}$ which we conjecture
to be sharp when $n^{2}\sigma^{d}\ll n$ (see Figure 2). This constant depends
very mildly on the geometrical properties of $\mathcal{P}$ and $\mathcal{Q}$
thus suggesting that when $n^{2}\sigma^{d}=o(n)$,
$\mathbb{E}\left[d_{H}\left({\hat{\pi}_{\mathrm{LSS}}},{\pi^{\star}}\right)\right]$
behaves as in the Gaussian model for a broad class of distributions.

The proof of Theorem 1.7 follows a similar strategy as in [11]. Given a
$t$-cycle $C_{t}=(i_{1},i_{2},\ldots,i_{t})$ of distinct elements from $[n]$
we say that it is an augmenting cycle (for $\hat{\pi}_{\mathrm{LSS}}$), or
just augmenting, if:

$\sum_{k=1}^{t}\langle
X_{\pi^{*}(i_{k})},Y_{i_{k+1}}\rangle\geq\sum_{k=1}^{t}\langle
X_{\pi^{*}(i_{k})},Y_{i_{k}}\rangle,$ (1.10)

where $i_{t+1}:=i_{1}$. If we assume that $\pi^{\star}=\text{Id}$, all cycles
of size $2$ or greater on the cycle decomposition of
$\hat{\pi}_{\mathrm{LSS}}$ will be mistakes. Moreover, these cycles must be
augmenting cycles, otherwise they would not appear in the optimal assignment
$\hat{\pi}_{\mathrm{LSS}}$. It follows that we have the following
deterministic bound:

$d_{H}\left({\hat{\pi}_{\mathrm{LSS}}},{\pi^{\star}}\right)\leq\sum_{t=2}^{n}\sum_{C_{t}}t\mathbf{1}_{[C_{t}\text{
is augmenting}]},$ (1.11)

where the inner sum is over all $t$-cycles $C_{t}$.

To bound
$\mathbb{E}\left[d_{H}\left({\hat{\pi}_{\mathrm{LSS}}},{\pi^{\star}}\right)\right]$,
we bound the probability that $t$-cycles are augmenting. Similarly to [11] our
upper bounds on these probabilities involve bounding the expectation of
exponentials of certain quadratic forms on the initial positions. Unlike in
the Gaussian setting of [11], we cannot evaluate these expectations
explicitly. Fortunately, the assumptions in LD+S are good enough for
calculations to go through.

In Section 2 we show that Theorems 1.1 and 1.7 can be combined to obtain
optimal rates for some natural choices of $\mathcal{P}$ and $\mathcal{Q}$. One
such rate is when both $\mathcal{P}$ and $\mathcal{Q}$ have continuous and
bounded densities with $d$ fixed. Another case is the Gaussian model studied
in [11] in the regime where $d=o(\log n)$, where our bounds are optimal up to
$n^{o(1)}$ factors. We additionally consider the cases of $\mathcal{P}$
uniform or from the Laplace family.

####  1.1.2 High-dimension

Our next results concern the high-dimensional setting. As mentioned above,
this is a natural toy model for deduplication and entity resolution between
high-dimensional datasets [5].

######  Model HD.

In this setup we let $n\to+\infty$ while making the following assumptions in
(1.1):

  1. (a)

$d=\omega(\log n)$.

  2. (b)

$X_{1},\dots,X_{n}=(\Sigma_{X})^{\frac{1}{2}}\tilde{X}_{1},\dots,(\Sigma_{X})^{\frac{1}{2}}\tilde{X}_{n}$
and
$Z_{1},\dots,Z_{n}=(\Sigma_{Z})^{\frac{1}{2}}\tilde{Z}_{1},\dots,(\Sigma_{Z})^{\frac{1}{2}}\tilde{Z}_{n}$
where:

    1. (i)

$\tilde{X}_{1},\dots,\tilde{X}_{n}$ are i.i.d. and independent from
$\tilde{Z}_{1},\dots,\tilde{Z}_{n}$, which are also i.i.d.

    2. (ii)

Both $\tilde{X}_{1}$ and $\tilde{Z}_{1}$ have independent coordinates with:

$\mathbb{E}[\tilde{X}_{1}[j]]=0,\ \mathbb{E}[\tilde{Z}_{1}[j]]=0,\,\forall
j\in[d],$ (1.12)

and,

$\max_{j\in[d]}\left\|{\tilde{X}_{1}[j]}\right\|_{\psi_{2}}\leq K_{X}\text{,
}\ \max_{j\in[d]}\left\|{\tilde{Z}_{1}[j]}\right\|_{\psi_{2}}\leq K_{Z},$
(1.13)

for constants $K_{X},K_{Z}>0$ that do not depend on $n$.

    3. (iii)

$\Sigma_{X}=\mathop{\mathrm{missing}}{diag}\left(\sigma_{X}[1],\dots,\sigma_{X}[d]\right)$
and
$\Sigma_{Z}=\mathop{\mathrm{missing}}{diag}\left(\sigma_{Z}[1],\dots,\sigma_{Z}[d]\right)$
are diagonal matrices with strictly positive diagonal entries.

We leave implicit the dependence on $n$ of the distribution of the $X_{i}$’s,
$Z_{i}$’s and $Y_{i}$’s as well as $\Sigma_{X}$ and $\Sigma_{Z}$. Under the
above model we have the following result:

######  Theorem 1.8 (Perfect recovery for LSS in high-dimensions (proof in
§4.2)).

Under HD, suppose
$\frac{\mathop{\mathrm{missing}}{tr}\left(\Sigma_{Z}\Sigma_{X}\right)}{\left\|{\Sigma_{Z}\Sigma_{X}}\right\|_{op}}=\omega(\log
n)$,
$\frac{\mathop{\mathrm{missing}}{tr}\left(\Sigma_{X}\right)}{\left\|{\Sigma_{X}}\right\|_{op}}=\omega(\log
n)$ and let,

$\tilde{\sigma}^{2}_{X}[j]=\frac{\sigma^{2}_{X}[j]}{\sum\limits_{k=1}^{d}\sigma^{2}_{X}[k]},\leavevmode\nobreak\
j\in[d].$ (1.14)

There exists an absolute constant $b_{\mathrm{HD}}>0$ such that if

$b_{\mathrm{HD}}K^{2}_{Z}\leq\log
n^{-1}\frac{\sum\limits_{j=1}^{d}\sigma^{2}_{X}[j]}{\left(\sum\limits_{j=1}^{d}\tilde{\sigma}^{2}_{X}[j]\sigma^{2}_{Z}[j]\right)}$
(1.15)

then $d_{H}\left({\hat{\pi}_{\mathrm{LSS}}},{\pi^{\star}}\right)=0$ with high
probability.

This theorem establishes a sufficient condition for perfect recovery for an
estimator which is agnostic to any information on the distribution of the
noise and its covariance structure. It extends the results on the high-
dimensional setting from [11]. This condition can be slightly improved if we
assume knowledge of $\Sigma_{Z}$. We consider a modified version of LSS,
LSS-C, which incorporates the information from $\Sigma_{Z}$. It is defined as:

$\displaystyle\hat{\pi}_{\mathrm{LSS-C}}$ $\displaystyle:=\underset{\pi\in
S_{n}}{\text{arg
min}}\sum_{j=1}^{n}\left\|{(\Sigma_{Z})^{-\frac{1}{2}}(X_{\pi(j)}-Y_{j})}\right\|_{2}^{2}$
(1.16) $\displaystyle=\underset{\pi\in S_{n}}{\text{arg
max}}\sum_{j=1}^{n}\left\langle(\Sigma_{Z})^{-1}X_{\pi(j)},Y_{j}\right\rangle.$

Regarding this estimator we have the following sufficient condition for
perfect recovery:

######  Theorem 1.9 (Perfect recovery for LSS-C in high-dimensions (proof in
§4.2)).

Under HD, suppose
$\frac{\mathop{\mathrm{missing}}{tr}\left((\Sigma_{Z})^{-1}\Sigma_{X}\right)}{\left\|{(\Sigma_{Z})^{-1}\Sigma_{X}}\right\|_{op}}=\omega(\log
n)$ and let $(\tilde{\sigma}^{2}_{X}[j])_{j=1}^{d}$ and $b_{\mathrm{HD}}$ be
as in Theorem 1.8. If

$\begin{split}b_{\text{HD}}K^{2}_{Z}&\leq\log
n^{-1}\frac{\sum\limits_{j=1}^{d}\sigma^{2}_{X}[j]}{\left(\sum\limits_{j=1}^{d}\tilde{\sigma}^{2}_{X}[j]\sigma^{-2}_{Z}[j]\right)^{-1}},\end{split}$
(1.17)

then $d_{H}\left({\hat{\pi}_{\mathrm{LSS-C}}},{\pi^{\star}}\right)=0$ with
high probability.

The terms on the right hand side of Equation 1.15 and Equation 1.17 play the
role of signal-to-noise ratios. When
$X_{1},\dots,X_{n}\stackrel{{\scriptstyle\text{iid}}}{{\sim}}\mathcal{N}(0,I_{d})$
and
$Z_{1},\dots,Z_{n}\stackrel{{\scriptstyle\text{iid}}}{{\sim}}\mathcal{N}(0,\sigma^{2}I_{d})$
they simplify to $\frac{d}{\log n\sigma^{2}}$ recovering the signal-to-noise
ratio from the high-dimensional setting in [11]. In [11] the authors
conjecture that for the Gaussian case there exists a phase transition as
$n\to+\infty$ from partial recovery (i.e.
$\mathbb{E}\left[d_{H}\left({\hat{\pi}_{\mathrm{LSS}}},{\pi^{\star}}\right)\right]=\Omega(n)$)
when $\frac{d}{\log n\sigma^{2}}<4$ to perfect recovery ( i.e.
$\mathbb{E}\left[d_{H}\left({\hat{\pi}_{\mathrm{LSS}}},{\pi^{\star}}\right)\right]=o(1)$)
when $\frac{d}{\log n\sigma^{2}}>4$. Similar to our results, they prove the
sufficient condition for perfect recovery. However showing sharp necessary
conditions for perfect recovery by $\hat{\pi}_{\mathrm{LSS}}$ when
$d=\omega(\log n)$ is still an open problem. In [24] Appendix E.1 the authors
show that when $d=\omega(\log n)$, any estimator that achieves strong recovery
(i.e.
$\mathbb{E}\left[d_{H}\left({\hat{\pi}_{\mathrm{LSS}}},{\pi^{\star}}\right)\right]=o(n)$)
must have $\frac{d}{\log n\sigma^{2}}>2$. This seems to settle the information
theoretic threshold for strong recovery in this regime as this condition is
conjectured to be sufficient for the greedy inner product algorithm studied in
[11] Appendix A.2 to achieve strong recovery.

The difference between Theorem 1.8 and Theorem 1.9 lies in how the variance of
the coordinates of the initial positions and noise interact. In Theorem 1.8
the noise term includes a weighted arithmetic mean of the variances of the
noise vector with weights given by the proportion of each coordinate on the
signal term. The noise term in Theorem 1.9 has a similar interpretation but
with a weighted harmonic mean. Since the harmonic mean is always smaller than
the arithmetic mean, the signal-to-noise term in Theorem 1.9 dominates the one
from Theorem 1.8, as expected. The conditions,

$\frac{\mathop{\mathrm{missing}}{tr}\left(\Sigma_{Z}\Sigma_{X}\right)}{\left\|{\Sigma_{Z}\Sigma_{X}}\right\|_{op}}=\omega(\log
n),\,\frac{\mathop{\mathrm{missing}}{tr}\left(\Sigma_{X}\right)}{\left\|{\Sigma_{X}}\right\|_{op}}=\omega(\log
n)\text{ and
}\frac{\mathop{\mathrm{missing}}{tr}\left((\Sigma_{Z})^{-1}\Sigma_{X}\right)}{\left\|{(\Sigma_{Z})^{-1}\Sigma_{X}}\right\|_{op}}=\omega(\log
n)$ (1.18)

are technical conditions on the stable rank of $\Sigma_{Z}\Sigma_{X}$,
$\Sigma_{X}$ and $(\Sigma_{Z})^{-1}\Sigma_{X}$ respectively. These conditions
roughly state that the sum of the entries of these diagonal matrices cannot be
too concentrated along a small subset of coordinates. All three conditions
necessarily require that $d=\omega(\log n)$. For $\Sigma_{X}$ this condition
can be interpreted as saying that we must effectively be in a high-dimensional
setting by ruling out scenarios where we might have $d=\omega(\log n)$ but our
signal is concentrated in a low-dimensional subspace. If $\Sigma_{X}$ is
isotropic, the first condition in (1.18) rules out the possibility of the
strength of noise being concentrated along a low-dimensional subset of
coordinates and the last condition rules out the possibility of there being a
small subset of coordinates with a level of noise much smaller than the other
ones.

Before proceeding, we note that the proofs of our high-dimensional results
also rely on the concept of augmenting cycles that was outlined in the
discussion of Theorem 1.7. The main difference is that we must use the Hanson-
Wright inequality to show that the quadratic forms on the initial positions
concentrate around their expected value. This allows us to obtain sharp
estimates as the dimension grows.

###  1.2 Organization

The remainder of the paper is organized as follows. In Section 1.3 we set our
notation. Section 2 presents examples that showcase some consequences of our
results when $d=o(\log n)$. In Section 3 we discuss matchings in random
geometric graphs and their application to minimax lower bounds. In particular,
this is where we prove Theorem 1.1 and Lemma 1.2. Section 4 discusses
augmenting cycles and proves our upper bound results in both low and high-
dimensions. Section 5 provides some directions for future work. The Appendix
contains comments on and extensions of the arguments in the main text.

###  1.3 Notation

Throughout this work we will use the following conventions:

General notation: $\mathbb{N},\mathbb{Z},\mathbb{R}$ denote the set of
positive integers, integers and real numbers respectively and for any
$m\in\mathbb{N}$, $[m]=\\{1,\dots,m\\}$.

Linear Algebra and Analysis: For a vector $v\in\mathbb{R}^{d}$ we denote its
$i$-th coordinate by $v[i]$ and its Euclidean norm by
$\left\|{v}\right\|_{2}$. $\|\,\cdot\,\|$ denotes an arbitrary norm on
$\mathbb{R}^{d}$. If $A$ is a $m\times n$ matrix, we denote by $A[i,j]$ the
entry at its $i$-th row and $j$-th column. $A[i,:]\in\mathbb{R}^{n}$ is the
$i$-th row and $A[:,j]\in\mathbb{R}^{m}$ is the $j$th column of $A$
represented as vectors. If $v\in\mathbb{R}^{n}$, $Av\in\mathbb{R}^{m}$ denotes
the matrix-vector product.

$\left\|{A}\right\|_{op}=\sup_{\|x\|=1}\left\|{Ax}\right\|_{2}\text{ and
}\mathop{\mathrm{missing}}{tr}\left(A\right)=\sum\limits_{k=1}^{n}A[k,k]$
(1.19)

are the operator norm and trace of $A$ respectively, while
$\left\|{A}\right\|_{2}$ is the Frobenius norm of $A$. If $B$ is another
$k\times l$ matrix, $A\otimes B$ denotes the Kronecker product between $A$ and
$B$. If $k=n$ then, $AB$ denotes the matrix product of $A$ and $B$, and if
$k=m$ and $l=n$,
$\left\langle{A},{B}\right\rangle=\mathop{\mathrm{missing}}{tr}\left(B^{T}A\right)$
is the inner product between $A$ and $B$.
$B_{\|\,\cdot\,\|}(v,s)=\\{x\in\mathbb{R}^{d};\leavevmode\nobreak\
\left\|{x-v}\right\|<s\\}$ is the open ball centered at $v$ with radius $s>0$
on norm $\|\,\cdot\,\|$. $\rho_{d}$ denotes the volume of
$B_{\|\,\cdot\,\|_{2}}(0,1)$ in dimension $d$. $\wedge,\vee$ denote the
minimum and maximum between two real numbers. $\log(x)$ denotes the natural
logarithm of $x>0$.

Discrete structures: $d_{H}\left({\omega},{\omega^{\prime}}\right)$ denotes
the Hamming distance between two strings $\omega$ and $\omega^{\prime}$ of
equal length. If $G=(V,E)$ is a graph then $V(G)$ and $E(G)$ denote its set of
vertices and edges respectively. $\binom{n}{k}$ is the binomial coefficient.
If $A$ is a discrete set we denote its cardinality by $|A|$. $S_{n}$ is the
group of permutations on $[n]$.

Asymptotic Notation: Let $a_{n}=\left(a_{n}\right)_{n\in\mathbb{N}}$ and
$b_{n}=\left(b_{n}\right)_{n\in\mathbb{N}}$ be two sequences of real real
numbers. The asymptotic notation $O(\cdot),o(\cdot),\omega(\cdot)$,
$\Omega(\cdot),\Theta(\cdot)$ has its standard meaning, $a_{n}\ll b_{n}$ and
$a_{n}\gg b_{n}$ are synonymous with $a_{n}=o(b_{n})$ and $b_{n}=o(a_{n})$
respectively. $a_{n}\sim b_{n}$ indicates that
$\frac{a_{n}}{b_{n}}\underset{n\to\infty}{\longrightarrow}1$.

Probability: $\mathbb{P}\left(\cdot\right)$ and $\mathbb{E}\left[\cdot\right]$
denote probabilities and expectations respectively. We say $Z\sim\mathcal{Q}$
if the random element $Z$ has law $\mathcal{Q}$ and
$Z_{1},\dots,Z_{n}\stackrel{{\scriptstyle\text{iid}}}{{\sim}}\mathcal{Q}$
indicates a sequence of independent and identically distributed (i.i.d.)
random elements with common law $\mathcal{Q}$. $\mathcal{N}(\mu,\Sigma)$
denotes a multivariate Gaussian distribution with mean $\mu\in\mathbb{R}^{d}$
and $d\times d$ covariance matrix $\Sigma$. $\text{Unif}(S_{n})$ is the
uniform distribution over $S_{n}$. If $Z\sim\mathcal{N}(0,1)$ then
$\Phi(x)=\mathbb{P}\left(Z\leq x\right)$ is the cumulative distribution
function of a standard Gaussian random variable $Z$. If $\mathcal{Q}_{1}$ and
$\mathcal{Q}_{2}$ are two probability distributions on $\mathcal{Z}_{1}$ and
$\mathcal{Z}_{2}$, $\mathcal{Q}_{1}\otimes\mathcal{Q}_{2}$ denotes the product
measure on $\mathcal{Z}_{1}\times\mathcal{Z}_{2}$ with marginals
$\mathcal{Q}_{1}$ and $\mathcal{Q}_{2}$. When
$\mathcal{Z}_{1}=\mathcal{Z}_{2}$,
$\left\|{\mathcal{Q}_{1}-\mathcal{Q}_{2}}\right\|_{TV}$ indicates the total
variation distance between $\mathcal{Q}_{1}$ and $\mathcal{Q}_{2}$.

We say that a sequence of events $A_{n}=\left(A_{n}\right)_{n\in\mathbb{N}}$
happens with high probability if $\mathbb{P}\left(A_{n}\right)=1-o(1)$. Given
a sequence $U_{n}=\left(U_{n}\right)_{n\in\mathbb{N}}$ of random variables, we
say that $U_{n}=\Theta(a_{n})$ with high probability if there exists absolute
constants $c$ and $C$, not depending on $n$, such that $ca_{n}\leq U_{n}\leq
Ca_{n}$ holds with high probability.

$U_{n}\overset{(\mathbb{P})}{\underset{n\to\infty}{\longrightarrow}}U,U_{n}\overset{\text{a.s.}}{\underset{n\to\infty}{\longrightarrow}}U\text{
and }U_{n}\overset{(d)}{\underset{n\to\infty}{\longrightarrow}}U$ (1.20)

denote convergence in probability, almost sure convergence and convergence in
law respectively. If $U^{\prime}$ is another random variable, then
$U\stackrel{{\scriptstyle d}}{{=}}U^{\prime}$ indicates equality in law.
$o_{p}(1)$ denotes a random quantity that converges to $0$ in probability as
$n\to+\infty$. $\left\|{U}\right\|_{\psi_{2}}$ denotes the sub-Gaussian norm
of $U$. If $V$ is a random vector,
$\left\|{V}\right\|_{\psi_{2}}=\sup_{\left\|{v}\right\|=1}\left\|{\left\langle{V},{v}\right\rangle}\right\|_{\psi_{2}}$
is the sub-Gaussian norm of $V$.

##  2 Examples in the low-dimensional regime

In this section we show that Theorem 1.1 and Theorem 1.7 can be used to derive
positive and negative results for multiple choices of distributions for the
$X_{i}$’s and $Z_{i}$’s.

###  2.1 Gaussian initial positions and noise

We first consider the Gaussian model from [11] and show that the rate obtained
for the MLE is informational theoretical optimal up to factors of order
$n^{o(1)}$. More precisely we have:

######  Proposition 2.1 (Low-dimension, Gaussian initial positions, Gaussian
noise).

In (1.1), let $d=o(\log n)$, $X_{1}\sim\mathcal{N}(0,I_{d})$ and
$Z_{1}\sim\mathcal{N}(0,\sigma^{2}I_{d})$. Then as $n\to+\infty$,

$\inf_{\hat{\pi}}\mathbb{E}\left[d_{H}\left({\hat{\pi}},{\pi^{\star}}\right)\right]=(n^{(2+o(1))}\sigma^{d})\wedge
n^{(1+o(1))}.$ (2.1)

###### Proof.

If we take $\mathcal{P}=\mathcal{N}(0,I_{d})$ and $R_{d}=\sqrt{2d}$, we have
that for all sufficiently large $d$, assumption a from LD holds with
$\|\,\cdot\,\|=\|\,\cdot\,\|_{2}$, $\gamma=\frac{1}{2}$ and $\beta=1$. If we
let $\mathcal{Q}=\mathcal{N}(0,I_{d})$, using Bretagnolle–Huber inequality [1]
and the formula for the Kullback-Leibler divergence between multivariate
Gaussian distributions we have:

$\begin{split}\left\|{\mathcal{Q}(v)\otimes\mathcal{Q}(-v)-\mathcal{Q}\otimes\mathcal{Q}}\right\|_{TV}&\leq
1-\frac{1}{2}\exp\left(-\left\|{v}\right\|_{2}^{2}\right),\end{split}$ (2.2)

and so assumption b holds with $\beta=2+\log(2)$. From Theorem 1.1 it follows
that:

$\inf_{\hat{\pi}}\mathbb{E}\left[d_{H}\left({\hat{\pi}},{\pi^{\star}}\right)\right]=\Omega\left((n^{(2-o(1))}\sigma^{d}))\wedge
n^{(1-o(1))}\right).$ (2.3)

Since $\left\|{f_{\mathcal{P}}}\right\|_{\infty}\leq(2\pi)^{-\frac{d}{2}}$ and
$\mathcal{Q}$ is sub-Gaussian and zero-mean, assumptions c and d are also
satisfied. It follows from Theorem 1.7 that,

$\inf_{\hat{\pi}}\mathbb{E}\left[d_{H}\left({\hat{\pi}},{\pi^{\star}}\right)\right]\leq\mathbb{E}\left[d_{H}\left({\hat{\pi}_{\mathrm{LSS}}},{\pi^{\star}}\right)\right]=O\left((n^{(2+o(1))}\sigma^{d}))\wedge
n^{(1+o(1))}\right),$ (2.4)

from which the result follows. ∎

Note that our upper bound for the Gaussian model is slightly worse than the
one in [11] because of an extra $n^{o(1)}$ factor. This is natural since our
results make use of less properties of the distribution of the noise. On other
other hand, if $d$ is fixed we can ignore the $n^{o(1)}$ terms in the exponent
and thus obtain that the optimal error rate is of order
$\Theta\left((n^{2}\sigma^{d})\wedge n\right)$. This in particular confirms
that the upper bound for the expected number of mistakes made by the greedy
distance algorithm analyzed in Appendix A.1 of [11] is sharp.

###  2.2 Fixed dimension, continuous initial positions and noise

If we take $d,\mathcal{P}$ and $\mathcal{Q}$ to be fixed with $n$ we can
establish the optimal rate for a much wider class of distributions. These
assumptions are very natural if one considers for instance the problem of
particle tracking.

######  Proposition 2.2 (Fixed dimension, continuous initial positions,
continuous and sub-Gaussian noise).

In (1.1), let $d$ be fixed, $X_{1}\sim\mathcal{P}$ and
$Z_{1}=\sigma\tilde{Z}_{1}$ for $\sigma>0$ and $\tilde{Z}_{1}\sim\mathcal{Q}$
with $\mathcal{P}$ and $\mathcal{Q}$ two fixed distributions in
$\mathbb{R}^{d}$ having bounded continuous densities, the latter also being
zero-mean and sub-Gaussian. Then, as $n\to+\infty$,

$\inf_{\hat{\pi}}\mathbb{E}\left[d_{H}\left({\hat{\pi}},{\pi^{\star}}\right)\right]=\Theta\left((n^{2}\sigma^{d})\wedge
n\right).$ (2.5)

###### Proof.

Since $f_{\mathcal{P}}$, the density of $\mathcal{P}$, is continuous, it
follows that for any choice of norm $\|\,\cdot\,\|$ there must exists
$v\in\mathbb{R}^{d}$ and $R_{d}>0$ such that:

$\inf_{\left\|{x-v}\right\|<R_{d}}f_{\mathcal{P}}(x)>0.$ (2.6)

Suppose without loss of generality that $v=0$, the case $v\neq 0$ is
analogous. Then assumption a from LD is satisfied with this same choice of
$\|\,\cdot\,\|$ and $R_{d}$ and with,

$\gamma=\mathcal{P}\left(B_{\|\,\cdot\,\|}(0,R_{d})\right)>0\text{ and
}\beta=\log(2)\vee\left(\frac{1}{d}\left(\log(\left\|{f_{\mathcal{P}}}\right\|_{\infty})-\log\left(\inf_{\left\|{x}\right\|<R_{d}}f_{\mathcal{P}}(x)\right)\right)\right).$
(2.7)

Also, we have:

$\left\|{\mathcal{Q}(v)\otimes\mathcal{Q}(-v)-\mathcal{Q}\otimes\mathcal{Q}}\right\|_{TV}=\frac{1}{2}\int_{\mathbb{R}^{d}\times\mathbb{R}^{d}}|f_{\mathcal{Q}}(z_{1}-v)f_{\mathcal{Q}}(z_{2}+v)-f_{\mathcal{Q}}(z_{1})f_{\mathcal{Q}}(z_{2})|dz_{1}dz_{2}.$
(2.8)

Since for each $z_{1},z_{2}\in\mathbb{R}^{d}$,
$f_{\mathcal{Q}}(z_{1}-v)f_{\mathcal{Q}}(z_{2}+v)\to
f_{\mathcal{Q}}(z_{1})f_{\mathcal{Q}}(z_{2})$ as $\left\|{v}\right\|\to 0$ due
to the continuity of $f_{\mathcal{Q}}$, it follows from Scheffé’s Lemma that
the integral on the right hand side of (2.8) goes to $0$. Taking $R_{d}$
smaller and $\beta$ larger if necessary, assumption b from LD also holds. Thus
Theorem 1.1 follows and
$\inf_{\hat{\pi}}\mathbb{E}\left[d_{H}\left({\hat{\pi}},{\pi^{\star}}\right)\right]=\Omega((n^{2}\sigma^{d})\wedge
n)$. Since $\left\|{f_{\mathcal{P}}}\right\|_{\infty}$ is finite (and thus
$\leq e^{\beta d}$ for some $\beta$) and we are assuming that $\mathcal{Q}$ is
zero-mean and sub-Gaussian,

$\inf_{\hat{\pi}}\mathbb{E}\left[d_{H}\left({\hat{\pi}},{\pi^{\star}}\right)\right]=O\left((n^{2}\sigma^{d})\wedge
n\right)$ (2.9)

follows from Theorem 1.7. ∎

Under the same assumptions we can also improve our constant in the upper
bounds from Theorem 1.7:

######  Proposition 2.3 (Improved error upper bound for LSS (proof in §4.1)).

Under the same assumptions as in Proposition 2.2, we have that for all $n\geq
2$,

$\mathbb{E}\left[d_{H}\left({\hat{\pi}_{\mathrm{LSS}}},{\pi^{\star}}\right)\right]\leq((\tau+o(n\sigma^{d}))(n^{2}\sigma^{d}))\wedge
n,$ (2.10)

for,

$\tau=\tau_{\mathcal{P},\mathcal{Q},d}=2^{-d}\rho_{d}\mathbb{E}\left[f_{\mathcal{P}}(X_{1})\right]\mathbb{E}\left[\|\tilde{Z}_{1}-\tilde{Z}_{2}\|_{2}^{d}\right],$
(2.11)

where $\rho_{d}$ is the volume of $B_{\left\|{\cdot}\right\|_{2}}(0,1)$.

We conjecture that our constant $\tau$ in Proposition 2.3 is sharp in the
regime where $n\sigma^{d}=o(1)$. This is supported by the simulations shown in
Figure 2. The interesting feature of this result, which is illustrated in the
same figure, is that when $n\sigma^{d}=o(1)$ the error rate depends very
weakly on the geometry of the distribution $\mathcal{Q}$, so distributions
with significantly different geometric structures give rise to an error rate
similar to the Gaussian model. When $\sigma^{d}n^{2}$ starts to have order
$\Omega(n)$, other geometric properties of $\mathcal{P}$ and $\mathcal{Q}$
seem to play crucial roles and the predicted value of $\tau n^{2}\sigma^{d}$
ceases to be a good approximation to
$\mathbb{E}\left[d_{H}\left({\hat{\pi}_{\mathrm{LSS}}},{\pi^{\star}}\right)\right]$
as suggested by the same figure.

(a) $d=2$

(b) $d=3$

Figure 2: Simulated experiments to estimate the error rate
$\frac{\mathbb{E}\left[d_{H}\left({\hat{\pi}_{\mathrm{LSS}}},{\pi^{\star}}\right)\right]}{n}$
as a function of $\sigma^{2}$ for different choices of $\mathcal{Q}$. We
consider (1.1) with $X_{1}\sim\mathcal{N}(0,I_{d})$ and
$Z_{1}=\sigma\tilde{Z}_{1}$ with four different choices for the distribution
of $\tilde{Z}_{1}$: $\tilde{Z}_{1}\sim\mathcal{N}(0,I_{d})$ (Gaussian),
$\tilde{Z}_{1}\sim\text{Unif}(\mathbb{S}^{d-1})$ (Spherical),
$\tilde{Z}_{1}\sim\text{Unif}([-\sqrt{3},\sqrt{3}]^{d})$ (Uniform) and
$\tilde{Z}_{1}\sim\text{Unif}(\\{-1,1\\}^{d})$ (Rademacher). We also plot
$\tau n^{2}\sigma^{d}$ (Gaussian prediction) for the value of $\tau$ from
Proposition 2.3 obtained for the Gaussian model. Although some of these
distributions do not directly satisfy the assumptions of Proposition 2.3, we
will see in Section 4.1 that the same result holds under weaker assumptions
which includes all examples shown in the figure. For choice of $\mathcal{Q}$
in the simulations we considered $n=100,\,d=2,3$ and took the average of
$\frac{d_{H}\left({\hat{\pi}_{\mathrm{LSS}}},{\pi^{\star}}\right)}{n}$ over
$10000$ independent trials. Both axis are plotted using log-scale. The code to
reproduce the figures can also be found at https://github.com/Lucas-
Schwengber/particle_tracking.

###  2.3 Uniformly distributed initial positions

We now consider a model where the initial positions are uniformly distributed
on the unit cube in $\mathbb{R}^{d}$ and we alow $d$ to grow slowly with $n$.

######  Proposition 2.4 (Low-dimension, uniform initial positions, noise with
i.i.d. sub-Gaussian coordinates).

In (1.1), let $d=o(\log n)$, $X_{1}\sim\mathrm{Unif}([-1,1]^{d})$ and
$Z_{1}=\sigma\tilde{Z}_{1}$, where $\sigma>0$,

$\tilde{Z}_{1}\sim\mathcal{Q}=\bigotimes\limits_{j=1}^{d}\mathcal{Q}^{\prime},$
(2.12)

for $\mathcal{Q}^{\prime}$ a zero-mean, sub-Gaussian distribution in
$\mathbb{R}$ such that:

$\sup_{|v|<1}\left\|{\mathcal{Q}^{\prime}(v)-\mathcal{Q}^{\prime}}\right\|_{TV}<1-\delta,$
(2.13)

for some $\delta\in(0,1)$. We have that as $n\to+\infty$,

$\inf_{\hat{\pi}}\mathbb{E}\left[d_{H}\left({\hat{\pi}},{\pi^{\star}}\right)\right]=(n^{(2+o(1))}\sigma^{d})\wedge
n^{(1+o(1))}.$ (2.14)

###### Proof.

Taking $\mathcal{P}=\text{Unif}([-1,1]^{d})$, assumption a from LD is
satisfied with $\|\,\cdot\,\|=\left\|{\,\cdot\,}\right\|_{\infty}$, $R_{d}=1$,
$\gamma=1$ and $\beta=\log(2)$. Using a simple coupling argument one can show
that the total variation distance of product measures satisfies:

$\left(1-\left\|{\mathcal{Q}_{1}\otimes\mathcal{Q}_{2}-\mathcal{Q}^{\prime}_{1}\otimes\mathcal{Q}^{\prime}_{2}}\right\|_{TV}\right)\geq\left(1-\left\|{\mathcal{Q}_{1}-\mathcal{Q}^{\prime}_{1}}\right\|_{TV}\right)\left(1-\left\|{\mathcal{Q}_{2}-\mathcal{Q}^{\prime}_{2}}\right\|_{TV}\right).$
(2.15)

Since $\mathcal{Q}$ from our assumption is a product measure, it follows that
condition b from LD holds with,

$\beta=\log(2)\vee\left(-2\log(\delta)\right),$ (2.16)

and so Theorem 1.1 holds and we have a lower bound of order
$\Omega((n^{(2-o(1))}\sigma^{d})\wedge n^{(1-o(1))})$. Since
$\mathcal{Q}^{\prime}$ is also zero-mean, sub-Gaussian and
$\left\|{f_{\mathcal{P}}}\right\|_{\infty}\leq 2^{-d}$, the assumptions from
LD+S also hold and thus the upper bound of order
$O((n^{(2+o(1))}\sigma^{d})\wedge n^{(1+o(1))})$ follows. ∎

###  2.4 Noise with a log-Lipschitz density

We consider a lower bound in the regime where $d=o(\log n)$ with initial
positions following a Laplace distribution and a distribution on the noise
which is compatible with this assumption.

######  Proposition 2.5 (Low-dimension, Laplace initial positions, noise with
log-Lipschitz density).

In (1.1), let $d=o(\log n)$ and assume that $X_{1}$ has a standard
multivariate Laplace distribution, i.e.,

$X_{1}[1],\dots,X_{1}[d]\stackrel{{\scriptstyle\text{iid}}}{{\sim}}\mathrm{Lap}(0,1),$
(2.17)

where $\mathrm{Lap}(0,1)$ is the standard Laplace distribution on
$\mathbb{R}$. Assume also that $\mathcal{Q}$ has a continuous density
$f_{\mathcal{Q}}$ such that $\log(f_{\mathcal{Q}})$ is $L$-Lipschitz on the
$\left\|{\,\cdot\,}\right\|_{1}$ norm. Then as $n\to+\infty$,

$\inf_{\hat{\pi}}\mathbb{E}\left[d_{H}\left({\hat{\pi}},{\pi^{\star}}\right)\right]=\Omega((n^{(2-o(1))}\sigma^{d})\wedge
n^{(1-o(1))}).$ (2.18)

###### Proof.

Note that $|X_{1}[j]|\sim\text{Exp}(1)$ and so $\left\|{X_{1}}\right\|_{1}$ is
sub-Exponential with $\mathbb{E}\left[\left\|{X_{1}}\right\|_{1}\right]=d$. It
follows that condition a from LD hold for sufficiently large $d$ taking
$R_{d}=2d,\gamma=\frac{1}{2}$ and $\beta=2$. Since $\mathcal{Q}$ has a
continuous density $f_{\mathcal{Q}}$ such that $\log(f_{\mathcal{Q}})$ is
$L$-Lipschitz on the $\left\|{\,\cdot\,}\right\|_{1}$ norm, we have that:

$\begin{split}D_{KL}(\mathcal{Q}\otimes\mathcal{Q}||\mathcal{Q}(v)\otimes\mathcal{Q}(-v))&=D_{KL}(\mathcal{Q}||\mathcal{Q}(v))+D_{KL}(\mathcal{Q}||\mathcal{Q}(-v))\\\
&=\int_{\mathbb{R}^{d}}(\log(f_{\mathcal{Q}}(z))-\log(f_{\mathcal{Q}}(z+v)))f_{\mathcal{Q}}(z)dz\\\
&+\int_{\mathbb{R}^{d}}(\log(f_{\mathcal{Q}}(z))-\log(f_{\mathcal{Q}}(z-v)))f_{\mathcal{Q}}(z)dz\\\
&\leq 2L\left\|{v}\right\|_{1}.\end{split}$ (2.19)

It follows by the Bretagnolle–Huber inequality that,

$\left\|{\mathcal{Q}(v)\otimes\mathcal{Q}(-v)-\mathcal{Q}\otimes\mathcal{Q}}\right\|_{TV}\leq
1-\frac{1}{2}\exp\left(-2L\left\|{v}\right\|_{1}\right),$ (2.20)

and so condition b holds taking $\beta=4L+\log(2)$. So Theorem 1.1 holds and
we have a lower bound of order $\Omega\left(n^{(2-o(1))}\sigma^{d})\wedge
n^{(1-o(1))}\right)$. ∎

A natural choice for $\mathcal{Q}$ in this case would be also a standard
Laplace distribution. One might wonder if in this case the order of the
expected number of mistakes obtained for $\hat{\pi}_{\mathrm{LSS}}$ is also
nearly sharp, as $\mathcal{Q}$ fails to be sub-Gaussian but it still is sub-
Exponential. Although our techniques to prove the upper bounds cannot be
directly extended to this case we believe the rate should have the same
behaviour, but leave this question for future work.

##  3 Lower bounds via matchings in Random Geometric Graphs

In this section we prove Theorem 1.1 and Lemma 1.2. We first introduce some
notation for this section. Given a finite collection of points
$\mathcal{X}_{n}=\\{x_{1},\dots,x_{n}\\}\subset\mathbb{R}^{d},r>0$ and a norm
$\|\,\cdot\,\|$ on $\mathbb{R}^{d}$, we define a geometric graph as a graph
$G(n,r,d,\|\,\cdot\,\|)=G(\mathcal{X}_{n},r,d,\|\,\cdot\,\|)$ with,

$V(G(n,r,d,\|\,\cdot\,\|))=[n]\text{ and
}E(G(n,r,d,\|\,\cdot\,\|))=\\{\\{i,j\\}\subseteq[n];\leavevmode\nobreak\ i\neq
j\text{ and }\left\|{x_{i}-x_{j}}\right\|<r\\}.$ (3.1)

Following the convention of the literature, we leave the dependence of $r$ and
$d$ on $n$ implicit. If we take:

$\mathcal{X}_{n}=\\{X_{1},\dots,X_{n}\\}\text{ with
}X_{1},\dots,X_{n}\stackrel{{\scriptstyle\text{iid}}}{{\sim}}\mathcal{P},$
(3.2)

where $\mathcal{P}$ is a distribution in $\mathbb{R}^{d}$, we call the
corresponding random graph $G(n,r,d,\|\,\cdot\,\|)$ a random geometric graph
(RGG). As noted previously, asymptotic properties of random geometric graphs
have been previously explored in several works, see for instance the book [15]
for results in fixed dimension and [7] for the high-dimensional regime (i.e.
$d=\omega(\log n)$).

Recall that a matching in a graph $G$ is a subset of edges $M\subset E(G)$
with no vertices in common, i.e. such that $e\cap e^{\prime}=\emptyset$ for
any pair of distinct $e,e^{\prime}$ from $M$. We let
$M_{r}=M_{r}(\mathcal{X}_{n})$ denote the largest matching on
$G(\mathcal{X}_{n},r,d,\|\,\cdot\,\|)$.

###  3.1 A general lower bound

The next result gives us a general method to move from large matchings in
$G(n,r,d,\|\,\cdot\,\|)$ to lower bounds on
$\inf_{\hat{\pi}}\mathbb{E}\left[d_{H}\left({\hat{\pi}},{\pi^{\star}}\right)\right]$.
For a distribution $\mathcal{Q}$ over $\mathbb{R}^{d}$, and a vector
$v\in\mathbb{R}^{d}$, let $\mathcal{Q}(v)$ denote the law of $\tilde{Z}+v$
where $\tilde{Z}\sim\mathcal{Q}$ and set:

$t_{s}(\mathcal{Q},\|\,\cdot\,\|)=t_{s}(\mathcal{Q}):=\left(1-\sup_{\|v\|<s}\left\|{\mathcal{Q}(v)\otimes\mathcal{Q}(-v)-\mathcal{Q}\otimes\mathcal{Q}}\right\|_{TV}\right).$
(3.3)

Our lower bound is as follows:

######  Lemma 3.1.

Let $x_{1},\dots,x_{n}\in\mathbb{R}^{d}$ be distinct. Given $\sigma>0$ set,

$Y_{i}=x_{\pi^{\star}(i)}+\sigma\tilde{Z}_{\pi^{\star}(i)},\leavevmode\nobreak\
i\in[n],$ (3.4)

where $\pi^{\star}\sim{\rm Unif}(S_{n})$ is generated uniformly at random and
(independently)
$\tilde{Z}_{1},\dots,\tilde{Z}_{n}\stackrel{{\scriptstyle\text{iid}}}{{\sim}}\mathcal{Q}$,
for $\mathcal{Q}$ a distribution over $\mathbb{R}^{d}$. Then, for any
estimator,

$\hat{\pi}=\hat{\pi}(x_{1},\dots x_{n},Y_{1},\dots,Y_{n})\in S_{n},$ (3.5)

the following holds:

$\mathbb{E}\left[d_{H}\left({\hat{\pi}},{\pi^{\star}}\right)\right]\geq\frac{|M_{r}|t_{\frac{r}{\sigma}}(\mathcal{Q})}{2},$
(3.6)

for $t_{s}(\mathcal{Q})$ as in (3.3) above and
$M_{r}=M_{r}(\\{x_{1},\dots,x_{n}\\})$ the largest matching in
$G(\\{x_{1},\dots,x_{n}\\},r,d,\|\,\cdot\,\|)$.

The Lemma above gives a lower bound which takes into account two effects:
$|M_{r}|$ accounts for pairs of close initial positions, while
$t_{\frac{r}{\sigma}}(\mathcal{Q})$ accounts for the difficulty of
distinguishing their associated noisy versions. The free parameter $r$
controls the trade-off between these two quantities: as $r$ increases we have
more matched initial positions but their noisy versions become more
distinguishable.

###### Proof of Lemma 3.1.

Given $v\in\mathbb{R}^{d}$ and $\sigma>0$ we let $\mathcal{Q}(v,\sigma)$
denote the law of $v+\sigma\tilde{Z}$ for $\tilde{Z}\sim\mathcal{Q}$. In
particular, $\mathcal{Q}(v)=\mathcal{Q}(v,1)$. We assume for ease of notation
that $M_{r}=\\{\\{2j-1,2j\\}\\}_{j=1}^{m}$, but the general case follows
analogously. Letting $\Omega=\\{0,1\\}^{m}$, we associate to each element of
$\Omega$ a permutation $\pi_{\omega}\in S_{n}$ given by:

$\pi_{\omega}=\prod_{j=1}^{m}((2j-1)2j)^{\omega_{j}}.$ (3.7)

In other words, $\pi_{\omega}$ swaps $(2j-1)$ and $2j$ if $\omega_{j}=1$ and
leave all other indices unchanged. Denote by $S_{\Omega}\subseteq S_{n}$ the
subset of permutations of this form. We associate to each $\omega\in\Omega$ a
probability measure $P_{\omega}$ on $(\mathbb{R}^{d})^{n}$ given by:

$P_{\omega}=\left(\bigotimes_{j=1}^{m}\left(\mathcal{Q}\left(x_{\pi_{\omega}(2j-1)},\sigma\right)\otimes\mathcal{Q}\left(x_{\pi_{\omega}(2j)},\sigma\right)\right)\right)\otimes\bigotimes_{k=2m+1}^{n}\mathcal{Q}\left(x_{k},\sigma\right).$
(3.8)

That is, letting $Y_{1},\dots,Y_{n}$ be random vectors with joint distribution
$P_{\omega}$, we have that for $j\in[m]$, if $\omega_{j}=0$ then,

$Y_{2j-1}=x_{2j-1}+\sigma\tilde{Z}_{2j-1},\
Y_{2j}=x_{2j}+\sigma\tilde{Z}_{2j},$ (3.9)

if $\omega_{j}=1$ then,

$Y_{2j-1}=x_{2j}+\sigma\tilde{Z}_{2j-1},\
Y_{2j}=x_{2j-1}+\sigma\tilde{Z}_{2j},$ (3.10)

and for $k=2m+1,\dots,n$,

$Y_{k}=x_{k}+\sigma\tilde{Z}_{k},$ (3.11)

where
$\tilde{Z}_{1},\dots,\tilde{Z}_{n}\stackrel{{\scriptstyle\text{iid}}}{{\sim}}\mathcal{Q}$.
Note that if $\omega$ and $\omega^{\prime}$ differ by a single coordinate $j$
then:

$\begin{split}\left\|{P_{\omega}-P_{\omega^{\prime}}}\right\|_{TV}&=\left\|{\mathcal{Q}\left(x_{\pi_{\omega}(2j-1)},\sigma\right)\otimes\mathcal{Q}\left(x_{\pi_{\omega}(2j)},\sigma\right)-\mathcal{Q}\left(x_{\pi_{\omega^{\prime}}(2j-1)},\sigma\right)\otimes\mathcal{Q}\left(x_{\pi_{\omega^{\prime}}(2j)},\sigma\right)}\right\|_{TV}\\\
&=\left\|{\mathcal{Q}\left(\frac{x_{\pi_{\omega}(2j-1)}}{\sigma}\right)\otimes\mathcal{Q}\left(\frac{x_{\pi_{\omega}(2j)}}{\sigma}\right)-\mathcal{Q}\left(\frac{x_{\pi_{\omega^{\prime}}(2j-1)}}{\sigma}\right)\otimes\mathcal{Q}\left(\frac{x_{\pi_{\omega^{\prime}}(2j)}}{\sigma}\right)}\right\|_{TV}\\\
&\leq\sup_{\left\|{v}\right\|<\frac{r}{\sigma}}\left\|{\mathcal{Q}(v)\otimes\mathcal{Q}(-v)-\mathcal{Q}\otimes\mathcal{Q}}\right\|_{TV}=1-t_{\frac{r}{\sigma}}(\mathcal{Q})\end{split}$
(3.12)

where the second equality and third inequality follow since the total
variation distance is invariant under translations and dilations respectively
and in the last inequality we also used the fact that $\|x_{2j}-x_{2j-1}\|<r$.
Suppose we observe $x_{1},\dots,x_{n}\in\mathbb{R}^{d}$ and
$Y_{1},\dots,Y_{n}\sim P_{\omega}$ from an unknown $\omega$. Given
$\hat{\omega}$ an estimator for $\omega$ based on $x_{1},\dots,x_{n}$ and
$Y_{1},\dots,Y_{n}$, it follows by Assouad’s Lemma [21] and (3.12) that:

$\inf_{\hat{\omega}}\max_{\omega\in\Omega}\mathbb{E}_{\omega}\left[d_{H}\left({\hat{\omega}},{\omega}\right)\right]\geq\frac{mt_{\frac{r}{\sigma}}(\mathcal{Q})}{2},$
(3.13)

where $\mathbb{E}_{\omega}\left[\,\cdot\,\right]$ denotes expectations under
$P_{\omega}$ and the infimum is taken over all (possibly non-deterministic)
estimators $\hat{\omega}$.

We can convert any estimator $\hat{\pi}$ for a hidden permutation
$\pi^{\star}$ based on $x_{1},\dots,x_{n}$ and $Y_{1},\dots,Y_{n}$ into an
estimator $\hat{\omega}^{(\hat{\pi})}$ for $\omega$ by setting:

$\hat{\omega}^{(\hat{\pi})}_{j}=\begin{cases}1,\leavevmode\nobreak\ \text{if
$\hat{\pi}(2j-1)=2j$ and $\hat{\pi}(2j)=2j-1$}\\\ 0,\leavevmode\nobreak\
\text{if $\hat{\pi}(2j-1)=2j-1$ and $\hat{\pi}(2j)=2j$}\\\
\epsilon,\leavevmode\nobreak\ \text{otherwise}\end{cases},$ (3.14)

where $\epsilon$ indicates an error regardless of the true $\omega_{j}$. For
any $\omega\in\Omega$, $\hat{\omega}^{(\hat{\pi})}_{j}\neq\omega_{j}$ implies
that $\hat{\pi}(2j)\neq\pi_{\omega}(2j)$ or
$\hat{\pi}(2j-1)\neq\pi_{\omega}(2j-1)$. It follows that:

$\begin{split}d_{H}\left({\hat{\pi}},{\pi_{\omega}}\right)&=\sum_{i=1}^{n}\mathbf{1}_{[\hat{\pi}(i)\neq\pi_{\omega}(i)]}\\\
&\geq\sum_{j=1}^{m}\mathbf{1}_{[\hat{\pi}(2j)\neq\pi_{\omega}(2j)]}+\mathbf{1}_{[\hat{\pi}_{\omega}(2j-1)\neq\pi_{\omega}(2j-1)]}\\\
&\geq d_{H}\left({\hat{\omega}^{(\hat{\pi})}},{\omega}\right),\end{split}$
(3.15)

and so,

$\inf_{\hat{\pi}}\max_{\pi_{\omega}\in
S_{\Omega}}\mathbb{E}\left[d_{H}\left({\hat{\pi}},{\pi_{\omega}}\right)|\pi^{\star}=\pi_{\omega}\right]\geq\frac{mt_{\frac{r}{\sigma}}(\mathcal{Q})}{2},$
(3.16)

where expectations are taken with respect to (3.4). Since $S_{\Omega}\subseteq
S_{n}$,

$\inf_{\hat{\pi}}\max_{\pi\in
S_{n}}\mathbb{E}\left[d_{H}\left({\hat{\pi}},{\pi}\right)|\pi^{\star}=\pi\right]\geq\frac{mt_{\frac{r}{\sigma}}(\mathcal{Q})}{2}.$
(3.17)

This proves the minimax lower bound. Note that we could take $\hat{\pi}$ to be
a non-deterministic estimator and the argument still follows. Also, due to the
structure of the problem, we always have that:

$\inf_{\hat{\pi}}\max_{\pi\in
S_{n}}\mathbb{E}\left[d_{H}\left({\hat{\pi}},{\pi}\right)|\pi^{\star}=\pi\right]=\inf_{\hat{\pi}}\mathbb{E}\left[d_{H}\left({\hat{\pi}},{\pi^{*}}\right)\right],$
(3.18)

where the infimum is taken over all (possibly non-deterministic) estimators
$\hat{\pi}$. We provide a proof of (3.18) on Appendix A in a more general
setting. From (3.18) the result follows. ∎

###  3.2 Matchings in random geometric graphs

Our next step to use Lemma 3.1 to prove Theorem 1.1 is proving Lemma 1.2. As
in the Introduction, we consider a random geometric graph
$G(n,r,d,\|\,\cdot\,\|)=G(\mathcal{X}_{n},r,d,\|\,\cdot\,\|)$ induced by
$\mathcal{X}_{n}=\\{X_{1},\dots,X_{n}\\}$, where
$X_{1},\dots,X_{n}\stackrel{{\scriptstyle\text{iid}}}{{\sim}}\mathcal{P}$ a
distribution with density $f_{\mathcal{P}}$ satisfying assumption a from LD.

###### Proof of Lemma 1.2.

Let

$l=\frac{2R_{d}e^{-\beta}}{(n-1)^{\frac{1}{d}}}.$ (3.19)

Assume first that $r\leq l$, which implies in particular that $r<R_{d}$ since
$\beta\geq\log(2)$. Let $B_{d}=B_{\|\,\cdot\,\|}\left(0,R_{d}\right)$ be such
that $\mathcal{P}\left(B_{d}\right)\geq\gamma>0$. Let $k_{n}$ be the maximum
number of non-overlapping (open) balls of radius $\frac{r}{2}$ (on norm
$\|\,\cdot\,\|$) that are entirely contained in $B_{d}$. Since $r<R_{d}$,
$k_{n}$ is at least the size of the largerst $r$-packing in
$B_{\|\,\cdot\,\|}\left(0,\frac{R_{d}}{2}\right)$. Following the volumetric
lower bound for the size of the $r$-packing number in [25, Theorem 14.2], we
obtain

$\left(\frac{R_{d}}{2r}\right)^{d}\leq k_{n}.$ (3.20)

Let $\mathcal{K}_{n}=\\{B_{i,d}\\}_{i=1}^{k_{n}}$ be a collection of $k_{n}$
non-overlapping balls of radius $\frac{r}{2}$ fully contained in $B_{d}$.
Denote by $N=|\mathcal{X}_{n}\cap B_{d}|$ the number of samples from
$\mathcal{X}_{n}=\\{X_{1},\dots,X_{n}\\}$ that fall inside $B_{d}$, and define

$U_{i,d}=\sum_{j=1}^{n}\mathbf{1}_{[X_{j}\in
B_{i,d}]}=\left|\mathcal{X}_{n}\cap B_{i,d}\right|,\leavevmode\nobreak\
i\in[k_{n}],$ (3.21)

the number of points from $\mathcal{X}_{n}$ that fall inside $B_{i,d}$. It is
clear that, conditionally on $N$, $U_{i,d}\sim\textnormal{Bin}(N,p_{i,d})$,
where $p_{i,d}=\mathbb{P}\left(X_{1}\in B_{i,d}|X_{1}\in B_{d}\right)$ for
each $i\in[k_{n}]$. Moreover,

$e^{-\beta d}\left(\frac{r}{2R_{d}}\right)^{d}\leq p_{i,d}\leq e^{\beta
d}\left(\frac{r}{2R_{d}}\right)^{d},$ (3.22)

since $\frac{\text{ess sup}_{x\in B_{d}}f_{\mathcal{P}}(x)}{\text{ess
inf}_{x\in B_{d}}f_{\mathcal{P}}(x)}\leq e^{\beta d}$ by assumption. Let

$I_{n}=\sum_{i=1}^{k_{n}}\mathbf{1}_{[U_{i,d}=2]},$ (3.23)

be the number of balls $B_{i,d}\in\mathcal{K}_{n}$ that have exactly $2$
elements from $\mathcal{X}_{n}$. Note that $|M_{r}|\geq I_{n}$ since we can
build a matching in $G(n,r,d,\|\,\cdot\,\|)$ by considering the edges between
each pair of points on the same $B_{i,d}$ such that $U_{i,d}=2$. Moreover, for
$k\in\\{0\\}\cup[n]$ and $n\geq 3$,

$\begin{split}\mathbb{P}\left(U_{i,d}=2|N=k\right)&=\binom{k}{2}p^{2}_{i,d}(1-p_{i,d})^{k-2}\\\
&\geq\binom{k}{2}p^{2}_{i,d}(1-p_{i,d})^{n-2}\\\
&\geq\binom{k}{2}\frac{e^{-2\beta
d}}{4}\left(\frac{r}{2R_{d}}\right)^{2d},\end{split}$ (3.24)

where we used (3.22) to bound $p_{i,d}$ above and below and also $e^{\beta
d}\left(\frac{r}{2R_{d}}\right)^{d}\leq\frac{1}{n-1}$ by our assumption that
$r\leq l$, and the fact that $(1-\frac{1}{(n-1)})^{n-1}\geq\frac{1}{4}$ if
$n\geq 3$. It follows that,

$\begin{split}\mathbb{P}\left(U_{i,d}=2\right)&=\mathbb{E}\left[\mathbb{P}\left(U_{i,d}=2|N\right)\right]\\\
&\geq\mathbb{E}\left[\binom{N}{2}\right]\frac{e^{-2\beta
d}}{4}\left(\frac{r}{2R_{d}}\right)^{2d}\\\
&\geq\gamma^{2}\binom{n}{2}\frac{e^{-2\beta
d}}{4}\left(\frac{r}{2R_{d}}\right)^{2d},\end{split}$ (3.25)

where in the last inequality we used the fact that
$N\sim\textnormal{Bin}(n,\mathbb{P}\left(X_{1}\in B_{d}\right))$ implies
$\mathbb{E}\left[\binom{N}{2}\right]=(\mathbb{P}\left(X_{1}\in
B_{d}\right))^{2}\binom{n}{2}$ and also $\mathbb{P}\left(X_{1}\in
B_{d}\right)\geq\gamma$ by assumption. So,

$\begin{split}\mathbb{E}\left[|M_{r}|\right]&\geq\mathbb{E}\left[I_{n}\right]\\\
&\geq k_{n}\gamma^{2}\binom{n}{2}\frac{e^{-2\beta
d}}{4}\left(\frac{r}{2R_{d}}\right)^{2d}\\\
&\geq\gamma^{2}\binom{n}{2}\frac{e^{-2\beta
d}}{4}\left(\frac{r}{8R_{d}}\right)^{d},\end{split}$ (3.26)

where the last inequality follows from (3.20). If $r>l$, then
$|M_{r}|\geq|M_{l}|$, and so,

$\begin{split}\mathbb{E}\left[|M_{r}|\right]&\geq\mathbb{E}\left[|M_{l}|\right]\\\
&\geq\gamma^{2}\binom{n}{2}\frac{e^{-2\beta
d}}{4}\left(\frac{l}{8R_{d}}\right)^{d}\\\
&=\gamma^{2}\frac{n}{2}\frac{e^{-2\beta d}}{4}e^{-\beta d}4^{-d}\\\
&=\gamma^{2}4^{-d}n\frac{e^{-3\beta d}}{8}.\end{split}$ (3.27)

Since $\binom{n}{2}\geq\frac{n^{2}}{4}$ for all $n\geq 2$, it follows that for
a general $r>0$,

$\mathbb{E}\left[|M_{r}|\right]\geq\frac{\gamma^{2}}{16}e^{-d(3\beta+\log(8))}\left(n^{2}\left(\frac{r}{R_{d}}\right)^{d}\wedge
n\right),$ (3.28)

and so the result follows. ∎

The size of the largest matching $M_{r}$ in $G(n,r,d,\|\,\cdot\,\|)$ cannot
exceed $\lfloor n/2\rfloor$ or the total number of edges of
$G(n,r,d,\|\,\cdot\,\|)$, $|E(G(n,r,d,\|\,\cdot\,\|))|$. This implies that:

$\mathbb{E}\left[|M_{r}|\right]\leq\mathbb{E}\left[|E(G(n,r,d,\|\,\cdot\,\|))|\right]\wedge\left\lfloor\frac{n}{2}\right\rfloor.$
(3.29)

A simple calculation shows that this implies:

$\mathbb{E}\left[|M_{r}|\right]\leq\left(\left\|{f_{\mathcal{P}}}\right\|_{\infty}\text{Vol}(B_{\|\,\cdot\,\|}(0,1))\,r^{d}\binom{n}{2}\right)\wedge\left\lfloor\frac{n}{2}\right\rfloor.$
(3.30)

It follows that for fixed $d$, the order from Lemma 1.2 is sharp.

###  3.3 Minimax lower bound

We now prove Theorem 1.1.

###### Proof of Theorem 1.1.

Under LD, using our assumptions on $\mathcal{P}$ and $\mathcal{Q}$ and
applying Lemma 1.2 to Lemma 3.1 with $r=R_{d}\sigma$, we have that whenever
$n\geq 3$,

$\inf_{\hat{\pi}}\mathbb{E}\left[d_{H}\left({\hat{\pi}},{\pi^{\star}}\right)\right]\geq\frac{\gamma^{2}}{32}e^{-7\beta
d}\left((n^{2}\sigma^{d})\wedge n\right).$ (3.31)

∎

##  4 Upper bounds

In this section we provide the technical results necessary to prove the upper
bounds in Theorem 1.7, Proposition 2.3, Theorem 1.8 and Theorem 1.9.

We first note that conditioned on $\pi^{\star}=\pi$, for some fixed $\pi\in
S_{n}$, the law of
$d_{H}\left({\hat{\pi}_{\mathrm{LSS}}},{\pi^{\star}}\right)$ is the same
regardless of the choice of $\pi$ [11]. So in this section, unless stated
otherwise, we assume without loss of generality that $\pi^{\star}=\text{Id}$.
Under this condition we will consider a $t$-cycle $C_{t}=(i_{1},\dots,i_{k})$
to be augmenting for $\hat{\pi}_{\mathrm{LSS}}$ if and only if:

$\sum_{k=1}^{t}\langle X_{i_{k}},Y_{i_{k+1}}\rangle\geq\sum_{k=1}^{t}\langle
X_{i_{k}},Y_{i_{k}}\rangle.$ (4.1)

The main content of the Lemmata we use to prove our upper bounds are bounds on
the probability that $t$-cycles are augmenting. Taking expectations on (1.11)
we can use these bounds to bound
$\mathbb{E}\left[d_{H}\left({\hat{\pi}_{\mathrm{LSS}}},{\pi^{\star}}\right)\right]$.

###  4.1 Upper bounds for low-dimension

Recall that a random variable $U$ is sub-Gaussian [22] if
$\left\|{U}\right\|_{\psi_{2}}<+\infty$, where:

$\left\|{U}\right\|_{\psi_{2}}:=\inf\left\\{L>0;\leavevmode\nobreak\
\mathbb{E}\left[\exp\left(\frac{U^{2}}{L^{2}}\right)\right]\leq 2\right\\}.$
(4.2)

Moreover, a random vector $V$ in $\mathbb{R}^{d}$ is sub-Gaussian if:

$\left\|{V}\right\|_{\psi_{2}}:=\sup_{\|v\|=1}\left\|{\langle
V,v\rangle}\right\|_{\psi_{2}}<+\infty.$ (4.3)

We have the following bound on the probability that a given $t$-cycle is
augmenting:

######  Lemma 4.1.

Under LD+S , for any $t$-cycle $C_{t}$,

$\mathbb{P}\left(C_{t}\text{ is augmenting}\right)\leq
2\left(K\sigma\right)^{d(t-1)},$ (4.4)

for
$K=b_{\mathrm{LD}}\left\|{f_{\mathcal{P}}}\right\|_{\infty}^{\frac{2}{d}}K_{\mathcal{Q}}^{2}e^{2\beta}$
where $b_{\mathrm{LD}}>0$ is an absolute constant.

###### Proof.

Let $\Delta_{1}:=X_{t}-X_{1}$, $\Delta_{i}:=X_{i-1}-X_{i},\leavevmode\nobreak\
i=2,\dots,t$, $\underaccent{\bar}{Z}\in\mathbb{R}^{t\times d}$ be a matrix
with entries $\underaccent{\bar}{Z}[i,j]=Z_{i}[j]$, i.e. the matrix whose rows
are given by $Z_{i}$, and define the matrices
$\underaccent{\bar}{\nnoise},\leavevmode\nobreak\
\underaccent{\bar}{\Delta},\leavevmode\nobreak\
\underaccent{\bar}{X}\in\mathbb{R}^{t\times d}$ analogously. We first assume
that $C_{t}=(1,2,\ldots,t)$. It is easy to see that $C_{t}$ will be augmenting
if and only if,

$\sum_{i=1}^{t}\langle\Delta_{i},Z_{i}\rangle\geq\frac{1}{2}\left(\sum_{i=1}^{t}\lVert\Delta_{i}\rVert_{2}^{2}\right).$
(4.5)

This is equivalent to,

$\langle\underaccent{\bar}{Z},\underaccent{\bar}{\Delta}\rangle\geq\frac{1}{2}\|\underaccent{\bar}{\Delta}\|_{2}^{2},$
(4.6)

and,

$\left\langle\underaccent{\bar}{\nnoise},\frac{\underaccent{\bar}{\Delta}}{\left\|{\underaccent{\bar}{\Delta}}\right\|_{2}}\right\rangle\geq\frac{1}{2}\frac{\left\|{\underaccent{\bar}{\Delta}}\right\|_{2}}{\sigma}.$
(4.7)

This last step is valid since
$\mathbb{P}\left(\left\|{\underaccent{\bar}{\Delta}}\right\|_{2}=0\right)=0$,
as $\mathcal{P}$ has no atoms, so we can also assume that
$\left\|{\underaccent{\bar}{\Delta}}\right\|_{2}\neq 0$. Let
$v_{1},\dots,v_{t}\in\mathbb{R}^{d}$ and
$\underaccent{\bar}{v}\in\mathbb{R}^{t\times d}$ with
$\underaccent{\bar}{v}[i,j]=v_{i}[j]$ and
$\left\|{\underaccent{\bar}{v}}\right\|_{2}=1$. We have that for some absolute
constant $\kappa>0$ and $K_{\mathcal{Q}}$,

$\begin{split}\left\|{\left\langle\underaccent{\bar}{\nnoise},\underaccent{\bar}{v}\right\rangle}\right\|_{\psi_{2}}^{2}&=\left\|{\sum_{i=1}^{t}\sum_{j=1}^{d}\underaccent{\bar}{\nnoise}[i,j]\underaccent{\bar}{v}[i,j]}\right\|_{\psi_{2}}^{2}\\\
&\leq\kappa\sum_{i=1}^{t}\left\|{\sum_{j=1}^{d}\tilde{Z}_{i}[j]v_{i}[j]}\right\|_{\psi_{2}}^{2}\\\
&=\kappa\sum_{i=1}^{t}\mathbf{1}_{[\left\|{v_{i}}\right\|_{2}\neq
0]}\left\|{v_{i}}\right\|_{2}^{2}\left\|{\left\langle\tilde{Z}_{i},\frac{v_{i}}{\left\|{v_{i}}\right\|_{2}}\right\rangle}\right\|_{\psi_{2}}^{2}\\\
&\leq\kappa K_{\mathcal{Q}}^{2}.\end{split}$ (4.8)

For any sub-Gaussian random variable $U$ we have that,

$\mathbb{P}\left(|U|\geq t\right)\leq
2e^{-\frac{t^{2}}{\left\|{U}\right\|_{\psi_{2}}^{2}}}.$ (4.9)

It follows that since $\underaccent{\bar}{\nnoise}$ and
$\underaccent{\bar}{\dpos}$ are independent,

$\begin{split}\mathbb{P}\left(\left\langle{\underaccent{\bar}{\nnoise}},{\frac{\underaccent{\bar}{\dpos}}{\left\|{\underaccent{\bar}{\Delta}}\right\|_{2}}}\right\rangle\geq\frac{1}{2}\frac{\left\|{\underaccent{\bar}{\Delta}}\right\|_{2}}{\sigma}\Big{\rvert}\underaccent{\bar}{\Delta}\right)&\leq
2\exp\left(-\frac{1}{4\kappa
K^{2}_{\mathcal{Q}}}\frac{\left\|{\underaccent{\bar}{\Delta}}\right\|_{2}^{2}}{\sigma^{2}}\right)\\\
&=2\exp\left(-\frac{1}{4\kappa
K^{2}_{\mathcal{Q}}}\frac{\sum\limits_{i=1}^{t}\left\|{\Delta_{i}}\right\|_{2}^{2}}{\sigma^{2}}\right)\\\
&\leq 2\exp\left(-\frac{1}{4\kappa
K^{2}_{\mathcal{Q}}}\frac{\sum\limits_{i=1}^{t-1}\left\|{\Delta_{i}}\right\|_{2}^{2}}{\sigma^{2}}\right),\end{split}$
(4.10)

where in the last inequality we used the fact that
$\left\|{\Delta_{t}}\right\|_{2}^{2}\geq 0$. Although this last step might
seem arbitrary we will see that it allows us to bound the expectation of the
expressions above by a Gaussian integral. Remember that $f_{\mathcal{P}}$
denotes the density of $X_{1}$ with respect to Lebesgue measure in
$\mathbb{R}^{d}$. Clearly $\underaccent{\bar}{X}$ also has a density with
respect to Lebesgue measure in $\mathbb{R}^{t\times d}$, but
$\underaccent{\bar}{\Delta}$ does not, since
$\sum_{i=1}^{t-1}\Delta_{i}=-\Delta_{t}$ and thus $\underaccent{\bar}{\Delta}$
takes values in a $((t-1)\times d)$-dimensional sub-space of
$\mathbb{R}^{t\times d}$. However, setting
$\underaccent{\bar}{\Delta}_{(t-1)}\in\mathbb{R}^{(t-1)\times d}$ to be
$\underaccent{\bar}{\Delta}$ without its $t$-th row, we have that
$\underaccent{\bar}{\Delta}_{(t-1)}$ has a density with respect to the
Lebesgue measure on $\mathbb{R}^{(t-1)\times d}$ given by:

$f_{\underaccent{\bar}{\Delta}_{(t-1)}}\left(b\right)=\int_{\mathbb{R}^{d}}\prod_{j=1}^{(t-1)}f_{\mathcal{P}}\left(x-\sum_{i=1}^{j}b[i,:]\right)f_{\mathcal{P}}(x)dx,\leavevmode\nobreak\
b\in\mathbb{R}^{(t-1)\times d}.$ (4.11)

In particular,

$\left\|{f_{\underaccent{\bar}{\Delta}_{(t-1)}}}\right\|_{\infty}\leq\int_{\mathbb{R}^{d}}\left\|{f_{\mathcal{P}}}\right\|_{\infty}^{(t-1)}f_{\mathcal{P}}(x)dx=\left\|{f_{\mathcal{P}}}\right\|_{\infty}^{(t-1)}.$
(4.12)

It follows that,

$\begin{split}\mathbb{P}\left(C_{t}\text{ is
augmenting}\right)&=\mathbb{E}\left[\mathbb{P}\left(\left\langle{\underaccent{\bar}{\nnoise}},{\frac{\underaccent{\bar}{\dpos}}{\left\|{\underaccent{\bar}{\Delta}}\right\|_{2}}}\right\rangle\geq\frac{1}{2}\frac{\left\|{\underaccent{\bar}{\Delta}}\right\|_{2}}{\sigma}\Big{\rvert}\underaccent{\bar}{\Delta}\right)\right]\\\
&\leq 2\int_{\mathbb{R}^{(t-1)\times d}}\exp\left(-\frac{1}{4\kappa
K^{2}_{\mathcal{Q}}}\frac{\sum\limits_{i=1}^{t-1}\left\|{b[i,:]}\right\|_{2}^{2}}{\sigma^{2}}\right)f_{\underaccent{\bar}{\Delta}_{(t-1)}}\left(b\right)db\\\
&\leq
2\|f_{\underaccent{\bar}{\Delta}_{(t-1)}}\|_{\infty}\int_{\mathbb{R}^{(t-1)\times
d}}\exp\left(-\frac{1}{4\kappa
K^{2}_{\mathcal{Q}}}\frac{\sum\limits_{i=1}^{t-1}\left\|{b[i,:]}\right\|_{2}^{2}}{\sigma^{2}}\right)db\\\
&\leq 2\left\|{f_{\mathcal{P}}}\right\|_{\infty}^{(t-1)}\left(4\pi\kappa
K^{2}_{\mathcal{Q}}\sigma^{2}\right)^{\frac{d(t-1)}{2}},\end{split}$ (4.13)

and so the result follows for $C_{t}=(1,2,\ldots,t)$ taking
$b_{\mathrm{LD}}=4\pi\kappa$. Since both $X_{1},\dots,X_{n}$ and
$Z_{1},\dots,Z_{n}$ have exchangeable distributions, the same argument follows
if we take $C_{t}$ to be any other $t$-cycle. ∎

We now proceed to prove the upper bound from Theorem 1.7.

###### Proof of Theorem 1.7.

Using (1.11) and Lemma 4.1, we have that,

$\displaystyle\mathbb{E}\left[d_{H}\left({\hat{\pi}_{\mathrm{LSS}}},{\pi^{\star}}\right)\right]$
$\displaystyle\leq\sum_{t=2}^{n}t\left|\\{C_{t};\leavevmode\nobreak\
C_{t}\text{ is a }t\text{-cycle}\\}\right|\mathbb{P}\left((1,\dots,t)\text{ is
augmenting}\right)$ (4.14)
$\displaystyle\leq\sum_{t=2}^{n}n^{t}\mathbb{P}\left((1,\dots,t)\text{ is
augmenting}\right)$ (4.15) $\displaystyle\leq
2K^{d}n^{2}\sigma^{d}\sum_{t=0}^{\infty}(K^{d}n\sigma^{d})^{t}$ (4.16)

where the second inequality follows since
$t\left|\\{C_{t};\leavevmode\nobreak\ C_{t}\text{ is a
}t\text{-cycle}\\}\right|=t\binom{n}{t}(t-1)!\leq n^{t}$. The upper bound in
(4.16) implies

$\mathbb{E}\left[d_{H}\left({\hat{\pi}_{\mathrm{LSS}}},{\pi^{\star}}\right)\right]\leq
3K^{d}n^{2}\sigma^{d}\leq n\mbox{ when }K^{d}n\sigma^{d}\leq\frac{1}{3}.$

On the other hand, when $K^{d}n\sigma^{d}>1/3$ we still have the trivial upper
bound
$\mathbb{E}\left[d_{H}\left({\hat{\pi}_{\mathrm{LSS}}},{\pi^{\star}}\right)\right]\leq
n$ because no estimator makes more than $n$ mistakes. Combining these
estimates finishes the proof.∎

The proof of the upper bound from Proposition 2.3 is very similar but we need
the following additional result:

######  Lemma 4.2.

Let $C_{2}=(i,j),\leavevmode\nobreak\ i,j\in[n]$ be any $2$-cycle and assume
$d$ is fixed in LD+S . Then,

$\lim_{\sigma\to 0}\frac{\mathbb{P}\left(C_{2}\text{ is
augmenting}\right)}{\sigma^{d}}=2^{-d}\rho_{d}\mathbb{E}\left[f_{\mathcal{P}}(X_{1})\right]\mathbb{E}\left[\left\|{\tilde{Z}_{1}-\tilde{Z}_{2}}\right\|_{2}^{d}\right],$
(4.17)

where $\rho_{d}$ is the volume of $B_{\left\|{\,\cdot\,}\right\|_{2}}(0,1)$,
$X_{1}\sim\mathcal{P}$ and
$\tilde{Z}_{1},\tilde{Z}_{2}\stackrel{{\scriptstyle\text{iid}}}{{\sim}}\mathcal{Q}$.

###### Proof.

Set $Z_{1}=\sigma\tilde{Z}_{1}$ and $Z_{2}=\sigma\tilde{Z}_{2}$ where
$\sigma>0$,
$\tilde{Z}_{1},\tilde{Z}_{2}\stackrel{{\scriptstyle\text{iid}}}{{\sim}}\mathcal{Q}$.
In view of (4.5),

$\begin{split}\mathbb{P}\left(C_{2}\text{ is
augmenting}\right)&=\mathbb{P}\left(\langle{Z_{1}-Z_{2}},{X_{1}-X_{2}}\rangle\geq\left\|{X_{1}-X_{2}}\right\|_{2}^{2}\right)\\\
&=\mathbb{P}\left(\left\|{\frac{Z_{1}-Z_{2}}{2}}\right\|_{2}\geq\left\|{\frac{Z_{1}-Z_{2}}{2}-(X_{1}-X_{2})}\right\|_{2}\right)\\\
&=\mathbb{P}\left(\left\|{\Delta_{Z}}\right\|_{2}\geq\left\|{\Delta_{Z}-\Delta_{X}}\right\|_{2}\right)\\\
&=\mathbb{P}\left(\left\|{\Delta_{Z}}\right\|_{2}\geq\left\|{\Delta_{Z}-\Delta_{X}}\right\|_{2},\leavevmode\nobreak\
\left\|{\Delta_{Z}}\right\|_{2}>0\right)\end{split}$ (4.18)

where $\Delta_{Z}=\frac{Z_{1}-Z_{2}}{2}$ and $\Delta_{X}=X_{1}-X_{2}$ and the
last equality follows since
$\mathbb{P}\left(\left\|{\Delta_{X}}\right\|_{2}=0\right)=0$ as $\mathcal{P}$
has no atoms. Let $f_{\Delta_{X}}$ be the density of $\Delta_{X}$, which
exists and is continuous since $f_{\mathcal{P}}$ is. We can rewrite (4.18) as:

$\mathbb{E}\left[\rho_{d}\left\|{\Delta_{Z}}\right\|_{2}^{d}\frac{\mathbb{P}\left(\left\|{\Delta_{Z}}\right\|_{2}\geq\left\|{\Delta_{Z}-\Delta_{X}}\right\|_{2}|\Delta_{Z}\right)}{\rho_{d}\left\|{\Delta_{Z}}\right\|_{2}^{d}}\mathbf{1}_{[\left\|{\Delta_{Z}}\right\|_{2}>0]}\right].$
(4.19)

Note that,

$\begin{split}\mathbb{P}\left(\left\|{\Delta_{Z}}\right\|_{2}\geq\left\|{\Delta_{Z}-\Delta_{X}}\right\|_{2}|\Delta_{Z}\right)&=\int_{B_{\left\|{\,\cdot\,}\right\|_{2}}\left(\Delta_{Z},\left\|{\Delta_{Z}}\right\|_{2}\right)}f_{\Delta_{X}}(x)dx\text{
a.s.}\end{split}$ (4.20)

Now, as $\sigma\to 0$,
$\left\|{\Delta_{Z}}\right\|_{2}\overset{\text{a.s.}}{\underset{n\to\infty}{\longrightarrow}}0$.
Since $f_{\Delta_{X}}$ is continuous it follows that,

$\lim_{\sigma\to
0}\frac{\mathbb{P}\left(\left\|{\Delta_{Z}}\right\|_{2}\geq\left\|{\Delta_{Z}-\Delta_{X}}\right\|_{2}|\Delta_{Z}\right)}{\rho_{d}\|\Delta_{Z}\|^{d}}\mathbf{1}_{[\left\|{\Delta_{Z}}\right\|_{2}>0]}=f_{\Delta_{X}}(0)\mathbf{1}_{[\left\|{\Delta_{Z}}\right\|_{2}>0]}\text{
a.s.}$ (4.21)

In particular, since
$\frac{\left\|{\Delta_{Z}}\right\|_{2}}{\sigma}=\left\|{\frac{\tilde{Z}_{1}-\tilde{Z}_{2}}{2}}\right\|_{2}$,

$\lim_{\sigma\to
0}\frac{\rho_{d}\left\|{\Delta_{Z}}\right\|_{2}^{d}}{\sigma^{d}}\frac{\mathbb{P}\left(\left\|{\Delta_{Z}}\right\|_{2}\geq\left\|{\Delta_{Z}-\Delta_{X}}\right\|_{2}|\Delta_{Z}\right)}{\rho_{d}\left\|{\Delta_{Z}}\right\|_{2}^{d}}\mathbf{1}_{[\left\|{\Delta_{Z}}\right\|_{2}>0]}=2^{-d}\rho_{d}\left\|{\tilde{Z}_{1}-\tilde{Z}_{2}}\right\|_{2}^{d}f_{\Delta_{X}}(0)\mathbf{1}_{[\left\|{\Delta_{Z}}\right\|_{2}>0]}\text{
a.s.}$ (4.22)

Note that
$f_{\Delta_{X}}(x)=\int_{\mathbb{R}^{d}}f_{\mathcal{P}}(y+x)f_{\mathcal{P}}(y)dy$,
so,

$\frac{\rho_{d}\left\|{\Delta_{Z}}\right\|_{2}^{d}}{\sigma^{d}}\frac{\mathbb{P}\left(\left\|{\Delta_{Z}}\right\|_{2}\geq\left\|{\Delta_{Z}-\Delta_{X}}\right\|_{2}|\Delta_{Z}\right)}{\rho_{d}\left\|{\Delta_{Z}}\right\|_{2}^{d}}\mathbf{1}_{[\left\|{\Delta_{Z}}\right\|_{2}>0]}\leq\rho_{d}\left\|{\frac{\tilde{Z}_{1}-\tilde{Z}_{2}}{2}}\right\|_{2}^{d}\|f_{\mathcal{P}}\|_{\infty}\mathbf{1}_{[\left\|{\Delta_{Z}}\right\|_{2}>0]}.$
(4.23)

By our sub-Gaussian assumption on $\mathcal{Q}$ we have that
$\mathbb{E}\left[\left\|{\tilde{Z}_{1}-\tilde{Z}_{2}}\right\|^{d}\right]<+\infty$.
So taking expectations on (4.22),

$\lim_{\sigma\to 0}\frac{\mathbb{P}\left(C_{2}\text{ is
augmenting}\right)}{\sigma^{d}}=2^{-d}\rho_{d}\mathbb{E}\left[\left\|{\tilde{Z}_{1}-\tilde{Z}_{2}}\right\|_{2}^{d}\right]f_{\Delta_{X}}(0),$
(4.24)

follows by the dominated convergence theorem. Since
$f_{\Delta_{X}}(0)=\mathbb{E}\left[f_{\mathcal{P}}(X_{1})\right]$, (4.17)
follows. ∎

The result above implies that $\mathbb{P}\left(C_{2}\text{ is
augmenting}\right)=\tau+o(\sigma^{d})$ for $\tau$ as in the right hand side of
(4.2). To obtain Proposition 2.3 we repeat the proof of Theorem 1.7 but use
this sharper estimate for $\mathbb{P}\left(C_{2}\text{ is augmenting}\right)$
on (4.14).

We believe the upper bound from Proposition 2.3 is sharp when
$\sigma^{d}n=o(1)$ since in this regime
$\mathbb{E}\left[d_{H}\left({\hat{\pi}_{\mathrm{LSS}}},{\pi^{\star}}\right)\right]$
seems to be roughly the expected the mass of augmenting $2$-cycles which is
$n^{2}\mathbb{P}\left(C_{2}\text{ is augmenting}\right)$. Since our sharp
estimate from Lemma 4.2 gives a sharp estimate on the latter quantity, it
should give a sharp estimate on
$\mathbb{E}\left[d_{H}\left({\hat{\pi}_{\mathrm{LSS}}},{\pi^{\star}}\right)\right]$.

######  Remark 4.3.

We note that in the proofs above we only needed to use assumption d from LD+S
on $\mathcal{Q}$. In particular, if we take $\mathcal{Q}$ to be as in the
examples shown in Figure 2, the results of this section still hold.

###  4.2 Upper bounds for high-dimensions

We now proceed to prove the upper bounds on the high-dimensional case from HD.
In this regime we also consider $\hat{\pi}_{\mathrm{LSS-C}}$ as defined in
(1.16). The same strategy of bounding the mass of augmenting cycles using
(1.11) also work for this estimator, but in this case a $t$-cycle $C_{t}$ is
augmenting if and only if:

$\sum_{k=1}^{t}\langle(\Sigma_{Z})^{-1}X_{i_{k}},Y_{i_{k+1}}\rangle\geq\sum_{k=1}^{t}\langle(\Sigma_{Z})^{-1}X_{i_{k}},Y_{i_{k}}\rangle.$
(4.25)

The upper bounds on the probability of a given cycle being augmenting under HD
are given by:

######  Lemma 4.4.

Let $\Delta_{1}:=X_{t}-X_{1}$, $\Delta_{i}:=X_{i-1}-X_{i}$ for $i=2,\dots,t$.
For any $t$-cycle $C_{t}$ we have that:

$\mathbb{P}\left(C_{t}\text{ is augmenting for
}\hat{\pi}_{\mathrm{LSS}}\right)\leq
2\mathbb{E}\left[\exp\left(-\frac{1}{4\kappa^{2}K^{2}_{Z}}\frac{\left(\sum\limits_{i=1}^{t}\left\|{\Delta_{i}}\right\|_{2}^{2}\right)^{2}}{\sum\limits_{i=1}^{t}\left\|{(\Sigma_{Z})^{\frac{1}{2}}\Delta_{i}}\right\|_{2}^{2}}\right)\right],$
(4.26)

and,

$\mathbb{P}\left(C_{t}\text{ is augmenting for
}\hat{\pi}_{\mathrm{LSS-C}}\right)\leq
2\mathbb{E}\left[\exp\left(-\frac{1}{4\kappa^{2}K^{2}_{Z}}\sum_{i=1}^{t}\left\|{(\Sigma_{Z})^{-\frac{1}{2}}\Delta_{i}}\right\|_{2}^{2}\right)\right],$
(4.27)

where $\kappa>0$ is an absolute constant and $K_{Z}>0$ is any constant
satisfying bii from HD.

###### Proof.

We prove again for $C_{t}=(1,2,\ldots,t)$ and the general case follows due to
the exchangeability of $X_{1},\dots,X_{n}$ and $Z_{1},\dots,Z_{n}$. Following
the proof of Lemma 4.1, $C_{t}$ will be augmenting for
$\hat{\pi}_{\mathrm{LSS}}$, if and only if:

$\sum_{i=1}^{t}\langle\Delta_{i},Z_{i}\rangle\geq\frac{1}{2}\left(\sum_{i=1}^{t}\left\|{\Delta_{i}}\right\|_{2}^{2}\right).$
(4.28)

Conditioned on $\Delta_{1},\dots,\Delta_{t}$, each
$\langle\Delta_{i},Z_{i}\rangle$ is a linear combination of independent zero-
mean sub-Gaussian random variables with,

$\begin{split}\left\|{\left\langle{\Delta_{i}},{Z_{i}}\right\rangle}\right\|_{\psi_{2}}^{2}&=\left\|{\left\langle{\Delta_{i}},{(\Sigma_{Z})^{\frac{1}{2}}(\Sigma_{Z})^{-\frac{1}{2}}Z_{1}}\right\rangle}\right\|_{\psi_{2}}^{2}\\\
&=\left\|{\left\langle(\Sigma_{Z})^{\frac{1}{2}}\Delta_{i},(\Sigma_{Z})^{-\frac{1}{2}}Z_{1}\right\rangle}\right\|_{\psi_{2}}^{2}\\\
&\leq\kappa\sum_{j=1}^{d}\left(\sigma_{Z}[j]\Delta_{i}[j]\right)^{2}\left\|{\tilde{Z}_{1}[j]}\right\|_{\psi_{2}}^{2}\\\
&\leq\kappa
K^{2}_{Z}\left\|{(\Sigma_{Z})^{\frac{1}{2}}\Delta_{i}}\right\|_{2}^{2},\end{split}$
(4.29)

for some absolute constant $\kappa>0$. It follows that (conditioned on
$\Delta$),

$\left\|{\sum_{i=1}^{t}\langle\Delta_{i},Z_{i}\rangle}\right\|_{\psi_{2}}^{2}\leq\kappa^{2}K^{2}_{Z}\sum_{i=1}^{t}\left\|{(\Sigma_{Z})^{\frac{1}{2}}\Delta_{i}}\right\|_{2}^{2}.$
(4.30)

Letting $\underaccent{\bar}{\dpos}$ be as in Lemma 4.1 we have that,

$\displaystyle\mathbb{P}\left(\sum_{i=1}^{t}\langle\Delta_{i},Z_{i}\rangle\geq\frac{1}{2}\left(\sum\limits_{i=1}^{t}\left\|{\Delta_{i}}\right\|_{2}^{2}\right)\Big{|}\underaccent{\bar}{\Delta}\right)$
$\displaystyle\leq
2\exp\left(-\frac{1}{4\kappa^{2}K^{2}_{Z}}\frac{\left(\sum\limits_{i=1}^{t}\left\|{\Delta_{i}}\right\|_{2}^{2}\right)^{2}}{\sum\limits_{i=1}^{t}\left\|{(\Sigma_{Z})^{\frac{1}{2}}\Delta_{i}}\right\|_{2}^{2}}\right).$
(4.31)

For $\hat{\pi}_{\mathrm{LSS-C}}$, $C_{t}$ will be augmenting if and only if,

$\sum_{i=1}^{t}\left\langle(\Sigma_{Z})^{-1}\Delta_{i},Z_{i}\right\rangle\geq\frac{1}{2}\left(\sum_{i=1}^{t}\left\|{(\Sigma_{Z})^{-\frac{1}{2}}\Delta_{i}}\right\|_{2}^{2}\right).$
(4.32)

In this case, conditioned on $\Delta_{i}$,

$\begin{split}\left\|{\left\langle{(\Sigma_{Z})^{-1}\Delta_{i}},{Z_{i}}\right\rangle}\right\|_{\psi_{2}}^{2}&=\left\|{\left\langle{(\Sigma_{Z})^{-\frac{1}{2}}\Delta_{i}},{(\Sigma_{Z})^{-\frac{1}{2}}Z_{1}}\right\rangle}\right\|_{\psi_{2}}^{2}\\\
&\leq\kappa\sum_{j=1}^{d}\left((\Sigma_{Z})^{-\frac{1}{2}}[j]\Delta_{i}[j]\right)^{2}\left\|{\tilde{Z}_{1}[j]}\right\|_{\psi_{2}}^{2}\\\
&\leq\kappa
K^{2}_{Z}\left\|{(\Sigma_{Z})^{-\frac{1}{2}}\Delta_{i}}\right\|_{2}^{2},\end{split}$
(4.33)

and so conditioned on $\Delta_{1},\dots,\Delta_{t}$,

$\left\|{\sum_{i=1}^{t}\langle(\Sigma_{Z})^{-1}\Delta_{i},Z_{i}\rangle}\right\|_{\psi_{2}}^{2}\leq\kappa^{2}K^{2}_{Z}\sum_{i=1}^{t}\left\|{(\Sigma_{Z})^{-\frac{1}{2}}\Delta_{i}}\right\|_{2}^{2}.$
(4.34)

Thus,

$\displaystyle\mathbb{P}\left(\sum_{i=1}^{t}\langle(\Sigma_{Z})^{-1}\Delta_{i},Z_{i}\rangle\geq\frac{1}{2}\left(\sum_{i=1}^{t}\left\|{(\Sigma_{Z})^{-\frac{1}{2}}\Delta_{i}}\right\|_{2}^{2}\right)|\underaccent{\bar}{\Delta}\right)$
$\displaystyle\leq
2\exp\left(-\frac{1}{4\kappa^{2}K^{2}_{Z}}\sum_{i=1}^{t}\left\|{(\Sigma_{Z})^{-\frac{1}{2}}\Delta_{i}}\right\|_{2}^{2}\right).$
(4.35)

Taking expected values with respect to $\Delta_{1},\dots,\Delta_{n}$ we have
the result. ∎

In order to estimate the expected values on the right hand side of (4.26) and
(4.27) we use the concentration of the norm of $\Delta_{1},\dots,\Delta_{t}$.
We do so with the following consequence of Hanson-Wright Inequality [16]:

######  Lemma 4.5.

Let $U_{1},\dots,U_{t}$, $t\geq 2$, be i.i.d. random vectors in
$\mathbb{R}^{d}$ with zero-mean, unit variance, independent sub-Gaussian
coordinates and let $D$ be a diagonal matrix with non-negative diagonal
entries. We have that for any $\epsilon>0$,

$\mathbb{P}\left(\left|\sum_{i=1}^{t}\|D^{\frac{1}{2}}\Xi_{i}\|^{2}_{2}-2t\mathop{\mathrm{missing}}{tr}\left(D\right)\right|\geq\varepsilon
2t\mathop{\mathrm{missing}}{tr}\left(D\right)\right)\leq
e^{-c_{1}\left(\frac{\varepsilon}{K^{2}}\right)2t\frac{\mathop{\mathrm{missing}}{tr}\left(D\right)}{\lVert
D\rVert_{op}}},$ (4.36)

where $\Xi_{1}:=U_{t}-U_{1}$, $\Xi_{i}:=U_{i-1}-U_{i}$ for $i=2,\dots,t$,
$\max_{j\in[d]}\left\|{U_{1}[j]}\right\|_{\psi_{2}}\leq K$ and
$c_{1}\left(\frac{\varepsilon}{K^{2}}\right)>0$ is a positive constant that
depends on $\frac{\varepsilon}{K^{2}}$.

###### Proof.

Let $U\in\mathbb{R}^{td}$ be a concatenation of $U_{1},U_{2},\dots,U_{t}$,
i.e.

$U[d(i-1)+j]=U_{i}[j],\text{ for }i\in[t]\text{ and }j\in[d].$ (4.37)

We first consider the case $t\geq 3$. Let $L^{C_{t}}$ and $E^{C_{t}}$ be the
Laplacian and incidence matrix respectively, of the cycle graph on $t$
vertices. Taking $A=\left(L^{C_{t}}\otimes D\right)$ and
$B=\left(E^{C_{t}}\otimes D^{\frac{1}{2}}\right)$ we have that $A=BB^{T}$. In
particular,

$\begin{split}\sum_{i=1}^{t}\|D^{\frac{1}{2}}\Xi\|^{2}_{2}&=\sum_{i=1}^{t}\left\langle{D^{\frac{1}{2}}\Xi_{i}},{D^{\frac{1}{2}}\Xi_{i}}\right\rangle\\\
&=\sum_{i=1}^{t}\sum_{j=1}^{d}\left(D^{\frac{1}{2}}[j,j]\Xi_{i}[j]\right)^{2}\\\
&=\left\langle{B^{T}U},{B^{T}U}\right\rangle\\\
&=\left\langle{AU},{U}\right\rangle.\end{split}$ (4.38)

Since the eigenvalues of $L^{C_{t}}$ are given by $4\sin^{2}\left(\frac{\pi
k}{t}\right),\leavevmode\nobreak\ k=0,\dots,t-1$ [14], we have that,

$\left\|{A}\right\|_{op}=\left\|{L^{C_{t}}}\right\|_{op}\left\|{D}\right\|_{op}=4\text{sin}^{2}\left(\frac{\pi\left\lceil\frac{t}{2}\right\rceil}{t}\right)\left\|{D}\right\|_{op}\leq
4\left\|{D}\right\|_{op}.$ (4.39)

Also,

$\left\|{A}\right\|_{2}^{2}=\left\|{L^{C_{t}}}\right\|_{2}^{2}\left\|{D}\right\|_{2}^{2}=6t\mathop{\mathrm{missing}}{tr}\left(D^{2}\right)\leq
6t\left\|{D}\right\|_{op}\mathop{\mathrm{missing}}{tr}\left(D\right),$ (4.40)

and,

$\mathop{\mathrm{missing}}{tr}\left(A\right)=2t\mathop{\mathrm{missing}}{tr}\left(D\right).$
(4.41)

Since $U$ has independent, zero-mean and unit variance coordinates we have
that
$\mathbb{E}\left[\left\langle{AU},{U}\right\rangle\right]=\mathop{\mathrm{missing}}{tr}\left(A\right)$.
It follows that using Hanson-Wright inequality,

$\displaystyle\mathbb{P}\left(\left|\left\langle{AU},{U}\right\rangle-\mathop{\mathrm{missing}}{tr}\left(A\right)\right|\geq\varepsilon\mathop{\mathrm{missing}}{tr}\left(A\right)\right)$
$\displaystyle\leq 2\exp\left(-c\leavevmode\nobreak\
\text{min}\left(\frac{\varepsilon^{2}\mathop{\mathrm{missing}}{tr}\left(A\right)^{2}}{K^{4}\left\|{A}\right\|_{2}^{2}},\frac{\varepsilon\mathop{\mathrm{missing}}{tr}\left(A\right)}{K^{2}\left\|{A}\right\|_{op}}\right)\right)$
(4.42) $\displaystyle\leq 2\exp\left(-c\leavevmode\nobreak\
\text{min}\left(\frac{\varepsilon^{2}(2t\mathop{\mathrm{missing}}{tr}\left(D\right))^{2}}{K^{4}6t\mathop{\mathrm{missing}}{tr}\left(D\right)\left\|{D}\right\|_{op}},\frac{\varepsilon
2t\mathop{\mathrm{missing}}{tr}\left(D\right)}{4K^{2}\left\|{D}\right\|_{op}}\right)\right)$
$\displaystyle=2\exp\left(-2t\frac{\mathop{\mathrm{missing}}{tr}\left(D\right)}{\left\|{D}\right\|_{op}}\leavevmode\nobreak\
c\leavevmode\nobreak\
\text{min}\left(\frac{\varepsilon^{2}}{3K^{4}},\frac{\varepsilon}{4K^{2}}\right)\right),$

for some absolut constant $c>0$. Following a similar reasoning, if $t=2$,
letting $A=2\left(L^{P_{2}}\otimes D\right)$, where $L^{P_{2}}$ is the
Laplacian of the path graph on $2$ vertices, we have:

$\begin{split}\sum_{i=1}^{2}\|D^{\frac{1}{2}}\Xi_{i}\|^{2}_{2}&=2\|D^{\frac{1}{2}}\Xi_{1}\|^{2}_{2}\\\
&=\left\langle{AU},{U}\right\rangle.\end{split}$ (4.43)

Since the eigenvalues of $L^{P_{t}}$ are $0$ and $2$ [14] we have,

$\left\|{A}\right\|_{op}=4\left\|{D}\right\|_{op},$ (4.44)
$\left\|{A}\right\|_{2}^{2}=16\mathop{\mathrm{missing}}{tr}\left(D^{2}\right)\leq
16\left\|{D}\right\|_{op}\mathop{\mathrm{missing}}{tr}\left(D\right),$ (4.45)

and,

$\mathop{\mathrm{missing}}{tr}\left(A\right)=4\mathop{\mathrm{missing}}{tr}\left(D\right).$
(4.46)

It follows that,

$\displaystyle\mathbb{P}\left(\left|\left\langle{AU},{U}\right\rangle-\mathop{\mathrm{missing}}{tr}\left(A\right)\right|\geq\varepsilon\mathop{\mathrm{missing}}{tr}\left(A\right)\right)$
$\displaystyle\leq 2\exp\left(-c\leavevmode\nobreak\
\text{min}\left(\frac{\varepsilon^{2}\mathop{\mathrm{missing}}{tr}\left(A\right)^{2}}{K^{4}\left\|{A}\right\|_{2}^{2}},\frac{\varepsilon\mathop{\mathrm{missing}}{tr}\left(A\right)}{K^{2}\left\|{A}\right\|_{op}}\right)\right)$
(4.47) $\displaystyle\leq 2\exp\left(-c\leavevmode\nobreak\
\text{min}\left(\frac{\varepsilon^{2}(4\mathop{\mathrm{missing}}{tr}\left(D\right))^{2}}{16K^{4}\mathop{\mathrm{missing}}{tr}\left(D\right)\left\|{D}\right\|_{op}},\frac{\varepsilon
4\mathop{\mathrm{missing}}{tr}\left(D\right)}{4K^{2}\left\|{D}\right\|_{op}}\right)\right)$
$\displaystyle\leq
2\exp\left(-4\frac{\mathop{\mathrm{missing}}{tr}\left(D\right)}{\left\|{D}\right\|_{op}}\leavevmode\nobreak\
c\leavevmode\nobreak\
\text{min}\left(\frac{\varepsilon^{2}}{4K^{4}},\frac{\varepsilon}{4K^{2}}\right)\right).$

The result follows by taking
$c_{1}\left(\frac{\varepsilon}{K^{2}}\right)=c\leavevmode\nobreak\
\text{min}\left(\frac{\varepsilon^{2}}{4K^{4}},\frac{\varepsilon}{4K^{2}}\right)$.
∎

We now prove Theorem 1.8 taking $b_{\text{HD}}:=2\kappa^{2}$.

###### Proof of Theorem 1.8.

Given $\varepsilon>0$ and $t\geq 2$, we have that,

$\displaystyle\mathbb{E}\left[\exp\left(-\frac{1}{4\kappa^{2}K^{2}_{Z}}\frac{\left(\sum\limits_{i=1}^{t}\left\|{\Delta_{i}}\right\|_{2}^{2}\right)^{2}}{\sum\limits_{i=1}^{t}\left\|{(\Sigma_{Z})^{\frac{1}{2}}\Delta_{i}}\right\|_{2}^{2}}\right)\right]$
$\displaystyle\leq\exp\left(-\frac{1}{4\kappa^{2}K^{2}_{Z}}\frac{(1-\varepsilon)^{2}}{(1+\varepsilon)}\frac{(2t\mathop{\mathrm{missing}}{tr}\left(\Sigma_{X}\right))^{2}}{(2t\mathop{\mathrm{missing}}{tr}\left(\Sigma_{Z}\Sigma_{X})\right)}\right)$
(4.48)
$\displaystyle+\mathbb{P}\left(\sum_{i=1}^{t}\left\|{\Delta_{i}}\right\|_{2}^{2}\leq(1-\varepsilon)2t\mathop{\mathrm{missing}}{tr}\left(\Sigma_{X}\right)\right)$
$\displaystyle+\mathbb{P}\left(\sum_{i=1}^{t}\left\|{(\Sigma_{Z})^{\frac{1}{2}}\Delta_{i}}\right\|_{2}^{2}\geq(1+\varepsilon)2t\mathop{\mathrm{missing}}{tr}\left(\Sigma_{Z}\Sigma_{X}\right)\right)$
$\displaystyle\leq\exp\left(-\frac{1}{4\kappa^{2}K^{2}_{Z}}\frac{(1-\varepsilon)^{2}}{(1+\varepsilon)}\frac{(2t\mathop{\mathrm{missing}}{tr}\left(\Sigma_{X}\right))^{2}}{(2t\mathop{\mathrm{missing}}{tr}\left(\Sigma_{Z}\Sigma_{X})\right)}\right)$
$\displaystyle+\exp\left(-2t\frac{\mathop{\mathrm{missing}}{tr}\left(\Sigma_{X}\right)}{\left\|{\Sigma_{X}}\right\|_{op}}c_{1}\left(\frac{\varepsilon}{(K_{X})^{2}}\right)\right)$
$\displaystyle+\exp\left(-2t\frac{\mathop{\mathrm{missing}}{tr}\left(\Sigma_{Z}\Sigma_{X}\right)}{\left\|{\Sigma_{Z}\Sigma_{X}}\right\|_{op}}c_{1}\left(\frac{\varepsilon}{(K_{X})^{2}}\right)\right),$

where the last inequality follows from Lemma 4.5 taking $U_{1}=\tilde{X}_{1}$
with $D=\Sigma_{X}$ and with $D=\Sigma_{Z}\Sigma_{X}$ respectively. Using the
same reasoning as in (4.15) it follows that,

$\displaystyle\mathbb{E}\left[d_{H}\left({\hat{\pi}_{\mathrm{LSS}}},{\pi^{\star}}\right)\right]$
$\displaystyle\leq\sum_{t=2}^{n}n^{t}\mathbb{P}\left((1,\dots,t)\text{ is
augmenting for }\hat{\pi}_{\mathrm{LSS}}\right)$ (4.49)
$\displaystyle\leq\sum_{t=2}^{n}2\exp(t\log
n)\mathbb{E}\left[\exp\left(-\frac{1}{4\kappa^{2}K^{2}_{Z}}\frac{\left(\sum\limits_{i=1}^{t}\left\|{\Delta_{i}}\right\|_{2}^{2}\right)^{2}}{\sum\limits_{i=1}^{t}\left\|{(\Sigma_{Z})^{\frac{1}{2}}\Delta_{i}}\right\|_{2}^{2}}\right)\right]$
(4.50) $\displaystyle\leq 2\sum\limits_{t=2}^{n}\exp\left(t\log
n\left(1-\frac{1}{2\kappa^{2}K^{2}_{Z}\log
n}\frac{(1-\varepsilon)^{2}}{(1+\varepsilon)}\frac{\mathop{\mathrm{missing}}{tr}\left(\Sigma_{X}\right)}{\frac{\mathop{\mathrm{missing}}{tr}\left(\Sigma_{Z}\Sigma_{X}\right)}{\mathop{\mathrm{missing}}{tr}\left(\Sigma_{X}\right)}}\right)\right)$
(4.51) $\displaystyle+2\sum_{t=2}^{n}\exp\left(t\log
n\left(1-2\frac{\mathop{\mathrm{missing}}{tr}\left(\Sigma_{X}\right)}{\log
n\left\|{\Sigma_{X}}\right\|_{op}}c_{1}\left(\frac{\varepsilon}{(K_{X})^{2}}\right)\right)\right)$
(4.52) $\displaystyle+2\sum_{t=2}^{n}\exp\left(t\log
n\left(1-2\frac{\mathop{\mathrm{missing}}{tr}\left(\Sigma_{Z}\Sigma_{X}\right)}{\log
n\left\|{\Sigma_{Z}\Sigma_{X}}\right\|_{op}}c_{1}\left(\frac{\varepsilon}{(K_{X})^{2}}\right)\right)\right)$
(4.53) $\displaystyle\leq 6\sum_{t=2}^{+\infty}e^{-t\omega(1)}=o(1),$ (4.54)

where the last equality is a consequence of our hypothesis taking
$b_{\mathrm{HD}}=2\kappa^{2}$. It follows by Markov’s inequality that we have
perfect recovery. ∎

The proof of Theorem 1.9 is analogous.

###### Proof of Theorem 1.9.

Note that,

$\displaystyle\mathbb{E}\left[\sum_{i=1}^{t}\lVert(\Sigma_{Z})^{-\frac{1}{2}}\Delta_{i}\rVert^{2}_{2}\right]$
$\displaystyle=2t\mathop{\mathrm{missing}}{tr}\left((\Sigma_{Z})^{-1}\Sigma_{X}\right).$
(4.55)

Given $\varepsilon>0$,

$\displaystyle\mathbb{E}\left[\exp\left(-\frac{1}{4\kappa^{2}K^{2}_{Z}}\sum_{i=1}^{t}\left\|{(\Sigma_{Z})^{-\frac{1}{2}}\Delta_{i}}\right\|_{2}^{2}\right)\right]$
$\displaystyle\leq\exp\left(-\frac{(1-\varepsilon)}{4\kappa^{2}K^{2}_{Z}}2t\mathop{\mathrm{missing}}{tr}\left((\Sigma_{Z})^{-1}\Sigma_{X}\right)\right)\leavevmode\nobreak\
$ (4.56)
$\displaystyle+\mathbb{P}\left(\sum_{i=1}^{t}\left\|{(\Sigma_{Z})^{-\frac{1}{2}}\Delta_{i}}\right\|_{2}^{2}\leq(1-\varepsilon)2t\mathop{\mathrm{missing}}{tr}\left((\Sigma_{Z})^{-1}\Sigma_{X}\right)\right).$

We can bound the last term using Lemma 4.5 once again with
$U_{1}=\tilde{X}_{1}$ and $D=(\Sigma_{Z})^{-1}\Sigma_{X}$ to estimate the last
probability above. We then have,

$\displaystyle\mathbb{E}\left[d_{H}\left({\hat{\pi}_{\mathrm{LSS-C}}},{\pi^{\star}}\right)\right]$
$\displaystyle\leq 2\sum_{t=2}^{n}\exp\left(t\log
n\right)\mathbb{E}\left[\exp\left(-\frac{1}{4\kappa^{2}K^{2}_{Z}}\sum_{i=1}^{t}\lVert(\Sigma_{Z})^{-\frac{1}{2}}\Delta_{i}\rVert^{2}_{2}\right)\right]$
$\displaystyle\leq 2\sum_{t=2}^{n}\exp\left(t\log
n\left(1-\frac{(1-\varepsilon)}{2\kappa^{2}K^{2}_{Z}\log
n}\mathop{\mathrm{missing}}{tr}\left((\Sigma_{Z})^{-1}\Sigma_{X}\right)\right)\right)$
$\displaystyle+2\sum_{t=2}^{n}\exp\left(t\log
n\left(1-2c_{1}\left(\frac{\varepsilon}{K_{X}^{2}}\right)\frac{\mathop{\mathrm{missing}}{tr}\left((\Sigma_{Z})^{-1}\Sigma_{X}\right)}{\log
n\left\|{(\Sigma_{Z})^{-1}\Sigma_{X}}\right\|_{op}}\right)\right)$
$\displaystyle\leq 4\sum_{t=2}^{+\infty}e^{-t\omega(1)}=o(1),$

where the last equality is again a consequence of our hypothesis taking
$b_{\mathrm{HD}}=2\kappa^{2}$. Once again we have perfect recovery following
Markov’s inequality. ∎

##  5 Future work

Besides the open problems already posed in [11], we propose the following
directions for future work:

######  Direction 5.1.

Although the minimax lower bounds established in this work hold under mild
assumptions on the tail of the noise distribution, we were only able to show
that they are optimal making the assumption that the noise is sub-Gaussian. A
natural follow-up question is what happens with noise distributions that do
not have sub-Gaussian tails. What are the minimal assumptions on the noise we
need to obtain rates of order $(n^{2}\sigma^{d})\wedge n$ as in Section 2? And
beyond these assumptions, what rates can be established for heavy-tailed
noise?

######  Direction 5.2.

Proving the following conjecture of independent interest:

######  Conjecture 5.3.

Given
$X_{1},\dots,X_{n}\stackrel{{\scriptstyle\text{iid}}}{{\sim}}\mathcal{P}_{n}$,
let $M_{r}$ be the largest matching in
$G(\\{X_{1},\dots,X_{n}\\},r,d,\|\,\cdot\,\|)$, where we allow both $r$ and
$d$ to scale with $n$. Assume,

$\mathbb{E}\left[E(G(n,r,d,\|\,\cdot\,\|))\right]=\binom{n}{2}\mathbb{P}\left(\|X_{1}-X_{2}\|_{2}^{2}<r^{2}\right)\underset{n\to\infty}{\longrightarrow}+\infty.$
(5.1)

Then:

$\mathbb{E}\left[|M_{r}|\right]=\Theta\left(\mathbb{E}\left[E(G(n,r,d,\|\,\cdot\,\|))\right]\wedge
n\right),$ (5.2)

and moreover the same order holds with high probability for $|M_{r}|$.

That is, the size of the largest matching in a random geometric graph is of
the order of the minimum between the expected number of edges of
$G(n,r,d,\|\,\cdot\,\|)$ and $n$. Proving this conjecture in the regime where
$d=\Theta(\log n)$ would allow us to partially recover the lower bound for the
logarithmic regime (i.e. $d=\Theta(\log n)$) from [11], following a more
general framework, as we outline in Appendix C.

## References

  * [1] J. Bretagnolle and C. Huber  “Estimation des densités : Risque minimax”  In _Séminaire de Probabilités XII_ Berlin, Heidelberg: Springer Berlin Heidelberg, 1978, pp. 342–363
  * [2] Shuxiao Chen et al.  “One-way matching of datasets with low rank signals”  In _arXiv preprint arXiv:2204.13858_ , 2022
  * [3] Nicolas Chenouard et al.  “Objective comparison of particle tracking methods”  In _Nature methods_ 11.3 Nature Publishing Group US New York, 2014, pp. 281–289
  * [4] M. Chertkov et al.  “Inference in particle tracking experiments by passing messages between images”  In _Proceedings of the National Academy of Sciences_ 107.17, 2010, pp. 7663–7668  DOI: 10.1073/pnas.0910994107
  * [5] P. Christen  “Data Matching: Concepts and Techniques for Record Linkage, Entity Resolution, and Duplicate Detection”, Data-Centric Systems and Applications  Springer Berlin Heidelberg, 2012  URL: https://books.google.com.br/books?id=LZrT6eWf9NMC
  * [6] Olivier Collier and Arnak S Dalalyan  “Minimax rates in permutation estimation for feature matching”  In _The Journal of Machine Learning Research_ 17.1 JMLR. org, 2016, pp. 162–192
  * [7] Luc Devroye, András György, Gábor Lugosi and Frederic Udina  “High-dimensional random geometric graphs and their clique number”, 2011
  * [8] Jian Ding, Yihong Wu, Jiaming Xu and Dana Yang  “The planted matching problem: Sharp threshold and infinite-order phase transition”  arXiv, 2021  DOI: 10.48550/ARXIV.2103.09383
  * [9] Khuloud Jaqaman et al.  “Robust single-particle tracking in live-cell time-lapse sequences”  In _Nature methods_ 5.8 Nature Publishing Group US New York, 2008, pp. 695–702
  * [10] H.. Kuhn  “The Hungarian method for the assignment problem”  In _Naval Research Logistics Quarterly_ 2.1-2, 1955, pp. 83–97  DOI: https://doi.org/10.1002/nav.3800020109
  * [11] Dmitriy Kunisky and Jonathan Niles-Weed  “Strong recovery of geometric planted matchings”  In _Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)_ , 2022, pp. 834–876  DOI: 10.1137/1.9781611977073.36
  * [12] Arthur La Porta et al.  “Fluid particle accelerations in fully developed turbulence”  In _Nature_ 409.6823 Nature Publishing Group UK London, 2001, pp. 1017–1019
  * [13] Mehrdad Moharrami, Cristopher Moore and Jiaming Xu  “The planted matching problem: Phase transitions and exact results”  In _The Annals of Applied Probability_ 31.6 Institute of Mathematical Statistics, 2021, pp. 2663–2720  DOI: 10.1214/20-AAP1660
  * [14] Bogdan Nica  “A Brief Introduction to Spectral Graph Theory”  EMS Press, 2018  DOI: 10.4171/188
  * [15] Mathew Penrose  “Random Geometric Graphs”  Oxford University Press, 2003  DOI: 10.1093/acprof:oso/9780198506263.001.0001
  * [16] Mark Rudelson and Roman Vershynin  “Hanson-wright inequality and sub-gaussian concentration”, 2013
  * [17] Guilhem Semerjian, Gabriele Sicuro and Lenka Zdeborová  “Recovery thresholds in the sparse planted matching problem”  In _Phys. Rev. E_ 102 American Physical Society, 2020, pp. 022304  DOI: 10.1103/PhysRevE.102.022304
  * [18] Hao Shen et al.  “Single particle tracking: from theory to biophysical applications”  In _Chemical reviews_ 117.11 ACS Publications, 2017, pp. 7331–7376
  * [19] Gabriele Sicuro  “Euclidean matching problems”  Springer, 2017
  * [20] Michel Talagrand  “Scaling and non-standard matching theorems”  In _Comptes Rendus Mathematique_ 356.6, 2018, pp. 692–695  DOI: https://doi.org/10.1016/j.crma.2018.04.018
  * [21] A.B. Tsybakov  “Introduction to Nonparametric Estimation”, Springer Series in Statistics  Springer New York, 2008  URL: https://books.google.com.br/books?id=mwB8rUBsbqoC
  * [22] Roman Vershynin  “High-Dimensional Probability: An Introduction with Applications in Data Science”, Cambridge Series in Statistical and Probabilistic Mathematics  Cambridge University Press, 2018  DOI: 10.1017/9781108231596
  * [23] Cédric Villani  “Optimal transport: old and new”  Springer, 2009
  * [24] Haoyu Wang, Yihong Wu, Jiaming Xu and Israel Yolou  “Random graph matching in geometric models: the case of complete graphs”  In _Conference on Learning Theory_ , 2022, pp. 3441–3488  PMLR
  * [25] Yihong Wu  “Lecture notes on: Information-theoretic methods for high-dimensional statistics”  URL: http://www.stat.yale.edu/~yw562/teaching/it-stats.pdf

##  Appendix A A technical result on estimation in groups

We prove the equality in (3.18), under a more general setting.

######  Lemma A.1.

Let $\\{P_{g}\\}_{g\in G}$ be a family of probability measures on some measure
space $\left(\mathcal{Z},\mathcal{A}\right)$, indexed by $G$ a finite group.
Assume that there exists a family of (measurable) mappings
$\\{T_{g}:\mathcal{Z}\to\mathcal{Z};\leavevmode\nobreak\ g\in G\\}$ such that
for any $g,h\in G$,

$Z\sim P_{g}\mbox{ implies }T_{h}(Z)\sim P_{gh}.$ (A.1)

Let $d_{G}:G\times G\to\mathbb{R}_{+}$ be a distance metric which is invariant
under right multiplication by a group element, i.e., for any
$g,g^{\prime},h\in G$,

$d_{G}(g,g^{\prime})=d_{G}(gh,g^{\prime}h).$ (A.2)

Let $g^{*}\sim\mathrm{Unif}(G)$ be a random group element and $Z\sim
P_{g^{*}}$. Then,

$\inf_{\hat{g}}\max_{g\in
G}\mathbb{E}\left[d_{G}(\hat{g}(Z),g^{*})|g^{*}=g\right]=\inf_{\hat{g}}\mathbb{E}\left[d_{G}(\hat{g}(Z),g^{*})\right],$
(A.3)

where the infimum is taken over all (possibly non-deterministic) estimators
$\hat{g}:\mathcal{Z}\to G$ of $g^{*}$.

###### Proof.

It is always the case that,

$\inf_{\hat{g}}\max_{g\in
G}\mathbb{E}\left[d_{G}(\hat{g}(Z),g^{*})|g^{*}=g\right]\geq\inf_{\hat{g}}\mathbb{E}\left[d_{G}(\hat{g}(Z),g^{*})\right].$
(A.4)

As for the other direction, let $\hat{g}$ be some (possibly non-deterministic)
estimator of $g^{*}$. Letting $\tilde{h}\sim\text{Unif}(G)$ be sampled
independently from $Z$ and $g^{*}$, set $\tilde{Z}=T_{\tilde{h}}(Z)$. Note
that $\tilde{Z}\sim P_{g^{*}\tilde{h}}$ by (A.1). Define a new non-
deterministic estimator:

$\check{g}(Z):=\hat{g}(\tilde{Z})\tilde{h}^{-1}.$ (A.5)

Due to the invariance of $d_{G}$,

$d_{G}(\check{g}(Z),g^{*})=d_{G}(\hat{g}(\tilde{Z}),g^{*}\tilde{h}).$ (A.6)

In particular, conditioned on $g^{*}=g$, $d_{G}(\check{g}(Z),g^{*})$ has the
same law as $d_{G}(\hat{g}(\tilde{Z}),g^{*}\tilde{h})$ and
$g^{*}\tilde{h}\sim\text{Unif}(G)$. Thus
$d_{G}(\hat{g}(\tilde{Z}),g^{*}\tilde{h})$ conditioned on $g^{*}=g$ has the
same law as $d_{G}(\hat{g}(Z),g^{*})$ with $g^{*}\sim\text{Unif}(G)$. It
follows that for any $g\in G$,

$\mathbb{E}\left[d_{G}(\check{g}(Z),g^{*})|g^{*}=g\right]=\mathbb{E}\left[d_{G}(\hat{g}(\tilde{Z}),g^{*}\tilde{h})|g^{*}=g\right]=\mathbb{E}\left[d_{G}(\hat{g}(Z),g^{*})\right],$
(A.7)

and so,

$\max_{g\in
G}\mathbb{E}\left[d_{G}(\check{g}(Z),g^{*})|g^{*}=g\right]\leq\mathbb{E}\left[d_{G}(\hat{g}(Z),g^{*})\right].$
(A.8)

From this it follows that,

$\inf_{\hat{g}}\max_{g\in
G}\mathbb{E}\left[d_{G}(\hat{g}(Z),g^{*})|g^{*}=g\right]\leq\inf_{\hat{g}}\mathbb{E}\left[d_{G}(\hat{g}(Z),g^{*})\right].$
(A.9)

∎

In the particular setting of Lemma 3.1 we have that Lemma A.1 holds with
$G=S_{n}$, $\mathcal{Z}=(\mathbb{R}^{d})^{n}$, $P_{\pi}$ the law of
$(Y_{1},\dots,Y_{n})$ where,

$Y_{i}:=x_{\pi(i)}+\sigma\tilde{Z}_{i},\leavevmode\nobreak\ i\in[n],$ (A.10)

for
$\tilde{Z}_{1},\dots,\tilde{Z}_{n}\stackrel{{\scriptstyle\text{iid}}}{{\sim}}Q$,
$d_{G}$ the Hamming distance and,

$T_{\alpha}(Y_{1},\dots,Y_{n}):=(Y_{\alpha(1)},\dots,Y_{\alpha(n)}).$ (A.11)

##  Appendix B Negative results in probability

In this section we show how one can use the same strategy from Section 3 to
derive high probability lower bounds for
$d_{H}\left({\hat{\pi}_{\mathrm{LSS}}},{\pi^{\star}}\right)$ that recover the
results from [11] up to $n^{o(1)}$ factors when $d=o(\log n)$, and also how it
can be used to establish negative results that complement the ones from [24].

###  B.1 High probability lower bounds on LSS

Our goal in this section is to prove the following high probability analogue
of Theorem 1.1 which partially recovers the lower bound from [11] when
$d=o(\log n)$, under greater generality:

######  Theorem B.1 (High probability lower bound on
$d_{H}\left({\hat{\pi}_{\mathrm{LSS}}},{\pi^{\star}}\right)$).

Consider a model as in (1.1) with $X_{1}\sim\mathcal{P}_{n}$ following
assumption a from LD for each $n$ for some $R_{d},\|\,\cdot\,\|,\gamma$ and
$\beta$, with $\beta$ and $\gamma$ that do not depend on $n$. Assume also that
$Z_{1}=\sigma\tilde{Z}_{1}$, where $\sigma>0$,
$\tilde{Z}_{1},\tilde{Z}_{2}\stackrel{{\scriptstyle\text{iid}}}{{\sim}}\mathcal{Q}_{n}$
a sequence of distributions in $\mathbb{R}^{d}$ such that,

$q_{R_{d}}(\mathcal{Q})=q_{R_{d}}(\mathcal{Q}_{n},\|\,\cdot\,\|):=\inf_{\left\|{v}\right\|=1}\mathbb{P}\left(\left\langle{\tilde{Z}_{1}-\tilde{Z}_{2}},{v}\right\rangle\geq
R_{d}\right)\geq e^{-\beta d},$ (B.1)

for the same $R_{d}$ and $\beta$ as in the assumption on $\mathcal{P}_{n}$. If
$e^{-10\beta d}\sigma^{d}n^{2}\underset{n\to\infty}{\longrightarrow}+\infty$
then with high probability,

$d_{H}\left({\hat{\pi}_{\mathrm{LSS}}},{\pi^{\star}}\right)\geq\frac{\gamma^{2}}{64}e^{-7\beta
d}\left((n^{2}\sigma^{d})\wedge n\right).$ (B.2)

For brevity we omit the dependence on $n$ of $\mathcal{P}_{n}$ and
$\mathcal{Q}_{n}$. We already know that if we assume $d$ and $\mathcal{P}$ to
be fixed with the latter having a bounded continuous density, assumption a is
verified. One can also verify that if $\mathcal{Q}$ is fixed with a bounded
continuous density then $q_{s^{*}}(\mathcal{Q})>0$ for some $s^{*}>0$, and
thus (B.1) also holds, thus giving us a high-probability lower bound of order
$(n^{2}\sigma^{d})\wedge n$ for
$d_{H}\left({\hat{\pi}_{\mathrm{LSS}}},{\pi^{\star}}\right)$. Similarly, if
$\mathcal{P}$ and $\mathcal{Q}$ follow the Gaussian model and $d=o(\log n)$
one can verify that the assumptions of Theorem B.1 also hold and obtain a high
probability lower bound of order $(n^{(2-o(1))}\sigma^{d})\wedge n^{(1-o(1))}$
for $d_{H}\left({\hat{\pi}_{\mathrm{LSS}}},{\pi^{\star}}\right)$.

As noted previously, when dealing with
$d_{H}\left({\hat{\pi}_{\mathrm{LSS}}},{\pi^{\star}}\right)$, augmenting
$2$-cycles are of particular interest as they seem to dominate the total mass
of augmenting $t$-cycles in the case of fixed dimension when
$\sigma^{d}=o\left(\frac{1}{n}\right)$, as seen in [11] and as suggested by
the proof of Theorem 1.7. As in [11], we let,

$G^{\text{aug}}=G^{\text{aug}}\left(n;X_{1},\dots,X_{n},Y_{1},\dots,Y_{n}\right),$
(B.3)

be the graph of augmenting $2$-cycles characterized by:

$V(G^{\text{aug}})=[n]\text{ and
}E(G^{\text{aug}})=\\{\\{i,j\\}\subseteq[n],\,(i,j)\text{ is an augmenting
cycle}\\}.$ (B.4)

Proving the existence of large matchings in $G^{\text{aug}}$ can be used to
prove lower bounds on
$\mathbb{E}\left[d_{H}\left({\hat{\pi}_{\mathrm{LSS}}},{\pi^{\star}}\right)\right]$
due to the following result from [11] (Proposition 4.1):

######  Lemma B.2.

Let $M^{*}$ be a largest matching in $G^{\text{aug}}$. We have,

$d_{H}\left({\hat{\pi}_{\mathrm{LSS}}},{\pi^{\star}}\right)\geq|M^{*}|.$ (B.5)

In order to show the existence of a large matching on $G^{\text{aug}}$,
instead of using an enhanced second moment argument as in [11], we use the
fact that a fraction of edges from the largest matching in
$G(n,d,r,\|\,\cdot\,\|)$ will also be augmenting cycles thus enabling us to
move from a large matching in the random geometric graph induced by the
initial positions to a large matching on the graph of augmenting $2$-cycles.
Since we are dealing with $\hat{\pi}_{\mathrm{LSS}}$, in this subsection
assume that $\pi^{\star}=\text{Id}$ as in Section 4. Letting
$\tilde{Z}_{1},\tilde{Z}_{2}\stackrel{{\scriptstyle\text{iid}}}{{\sim}}\mathcal{Q}$,
set:

$q_{s}(\mathcal{Q})=q_{s}(\mathcal{Q},\|\,\cdot\,\|):=\inf_{\left\|{v}\right\|=1}\mathbb{P}\left(\left\langle{\tilde{Z}_{1}-\tilde{Z}_{2}},{v}\right\rangle\geq
s\right).$ (B.6)

We have the following high-probability analogue of Lemma 3.1 for
$d_{H}\left({\hat{\pi}_{\mathrm{LSS}}},{\pi^{\star}}\right)$:

######  Lemma B.3.

Let $x_{1},\dots,x_{n}\in\mathbb{R}^{d}$ be distinct and set:

$Y_{i}:=x_{i}+\sigma\tilde{Z}_{i},\leavevmode\nobreak\ i\in[n],$ (B.7)

where
$\tilde{Z}_{1},\dots,\tilde{Z}_{n}\stackrel{{\scriptstyle\text{iid}}}{{\sim}}\mathcal{Q}$
and $\sigma>0$. Let $q_{s}(\mathcal{Q})$ be as in (B.6) above and
$M_{r}=M_{r}(\\{x_{1},\dots,x_{n}\\})$ the largest matching in
$G(\\{x_{1},\dots,x_{n}\\},r,d,\left\|{\,\cdot\,}\right\|_{2})$. If
$|M_{r}|q_{\frac{r}{\sigma}}(\mathcal{Q})\underset{n\to\infty}{\longrightarrow}+\infty$,
then,

$d_{H}\left({\hat{\pi}_{\mathrm{LSS}}},{\pi^{\star}}\right)\geq\frac{|M_{r}|q_{\frac{r}{\sigma}}(\mathcal{Q})}{2}$
(B.8)

with high probability.

###### Proof.

Let
$G^{\text{aug}}=G^{\text{aug}}\left(n;x_{1},\dots,x_{n},Y_{1},\dots,Y_{n}\right)$
be the graph of augmenting $2$-cycles and let $M^{*}$ denote its largest
matching. Given $\\{i,j\\}\in M_{r}$,

$\begin{split}\mathbb{P}\left(\\{i,j\\}\text{ is an edge on
}G^{\text{aug}}\right)&=\mathbb{P}\left(\left\langle{\tilde{Z}_{i}-\tilde{Z}_{j}},{\frac{x_{i}-x_{j}}{\left\|{x_{i}-x_{j}}\right\|}}\right\rangle\geq\frac{\|x_{i}-x_{j}\|}{\sigma}\right)\\\
&\geq\mathbb{P}\left(\left\langle{\tilde{Z}_{i}-\tilde{Z}_{j}},{\frac{x_{i}-x_{j}}{\left\|{x_{i}-x_{j}}\right\|}}\right\rangle\geq\frac{r}{\sigma}\right)\\\
&\geq q_{\frac{r}{\sigma}}(\mathcal{Q}).\end{split}$ (B.9)

Let
$H\sim\textnormal{Bin}\left(|M_{r}|,q_{\frac{r}{\sigma}}(\mathcal{Q})\right)$.
Using a simple coupling argument we get the bound:

$|M^{*}|\geq\sum_{e\in M_{r}}\mathbf{1}_{[e\in G^{\text{aug}}]}\geq H.$ (B.10)

Given our hypothesis we have that,

$\mathbb{P}\left(\bigl{\lvert}H-\mathbb{E}\left[H\right]\bigr{\rvert}\geq\varepsilon\mathbb{E}\left[H\right]\right)\leq\frac{|M_{r}|q_{\frac{r}{\sigma}}(\mathcal{Q})(1-q_{\frac{r}{\sigma}}(\mathcal{Q}))}{\varepsilon^{2}|M_{r}|^{2}q^{2}_{\frac{r}{\sigma}}(\mathcal{Q})}\leq\frac{1}{\varepsilon^{2}|M_{r}|q_{\frac{r}{\sigma}}(\mathcal{Q})}\underset{n\to\infty}{\longrightarrow}0.$
(B.11)

It follows that for any $\varepsilon>0$ we have that
$H\geq(1-\varepsilon)|M_{r}|q_{\frac{r}{\sigma}}$ with high probability and so
the result follows using Lemma B.2. ∎

We now show that our lower bound on $\mathbb{E}\left[|M_{r}|\right]$ from
Lemma 1.2 also holds with high probability:

######  Lemma B.4.

Let $X_{1},\dots,X_{n}\stackrel{{\scriptstyle\text{iid}}}{{\sim}}\mathcal{P}$
and $M_{r}$ be the largest matching in
$G(\\{X_{1},\dots,X_{n}\\},r,d,\|\,\cdot\,\|)$ and assume that for each $n$
assumption a from LD holds for $\mathcal{P}$ and some
$\|\,\cdot\,\|,R_{d},\gamma$ and $\beta$, with $\beta$ and $\gamma$ that do
not depend on $n$. If $e^{-9\beta
d}\left(\frac{r}{R_{d}}\right)^{d}n^{2}\underset{n\to\infty}{\longrightarrow}+\infty$,
then with high probability,

$|M_{r}|\geq\frac{\gamma^{2}}{32}e^{-6\beta
d}\left(\left(n^{2}\left(\frac{r}{R_{d}}\right)^{d}\right)\wedge n\right).$
(B.12)

###### Proof.

Letting once again,

$l=\frac{2R_{d}e^{-\beta}}{(n-1)^{\frac{1}{d}}},$ (B.13)

assume first that $r\leq l$, and thus $r<R_{d}$. Let $N,B_{d},p_{i,d}$,
$U_{i,d}$ and $I_{n}$ be as in the proof of Lemma 1.2. We will verify that
$I_{n}$ concentrates around its expected value $\mathbb{E}\left[I_{n}\right]$.
Using Chevyshev’s inequality, it suffices to show that:

$\frac{\mathbb{E}\left[I^{2}_{n}\right]}{\mathbb{E}\left[I_{n}\right]^{2}}\underset{n\to\infty}{\longrightarrow}1.$
(B.14)

Note that,

$\mathbb{E}\left[I^{2}_{n}\right]=\sum_{j=1}^{k_{n}}\sum_{i=1}^{k_{n}}\mathbb{P}\left(U_{i,d}=2,U_{j,d}=2\right)$
(B.15)

and

$\mathbb{E}\left[I_{n}\right]^{2}=\sum_{j=1}^{k_{n}}\sum_{i=1}^{k_{n}}\mathbb{P}\left(U_{i,d}=2\right)\mathbb{P}\left(U_{j,d}=2\right).$
(B.16)

Also, using (3.22) and (3.20),

$\sum_{i=1}^{k_{n}}\mathbb{P}\left(U_{i,d}=2\right)^{2}\leq\sum_{i=1}^{k_{n}}\mathbb{P}\left(U_{i,d}=2\right)\leq\binom{n}{2}e^{2\beta
d}\left(\frac{r}{8R_{d}}\right)^{d}.$ (B.17)

On the other hand, for $k_{n}\geq 2$, letting $q=\mathbb{P}\left(X_{1}\in
B_{d}\right)$,

$\begin{split}\mathbb{E}\left[I_{n}\right]^{2}&\geq\sum_{i=1}^{k_{n}}\sum_{j\in[k_{n}]\backslash\\{i\\}}\mathbb{P}\left(U_{i,d}=2\right)\mathbb{P}\left(U_{j,d}=2\right)\\\
&\geq\frac{k^{2}_{n}}{2}q^{4}\binom{n}{2}^{2}\frac{e^{-4\beta
d}}{16}\left(\frac{r}{2R_{d}}\right)^{4d}\\\ &\geq
q^{4}\binom{n}{2}^{2}\frac{e^{-4\beta
d}}{32}\left(\frac{r}{8R_{d}}\right)^{2d}\\\ &\gg\binom{n}{2}e^{2\beta
d}\left(\frac{r}{8R_{d}}\right)^{d},\end{split}$ (B.18)

since $e^{-9\beta
d}\left(\frac{r}{R_{d}}\right)^{d}n^{2}\underset{n\to\infty}{\longrightarrow}+\infty$
by assumption. Since
$\mathbb{E}\left[I^{2}_{n}\right]\geq\mathbb{E}\left[I_{n}\right]^{2}$, it
follows that both sums (B.15) and $\eqref{eq:sum_2}$ are dominated by the sums
over terms with $i,j\in[k_{n}]$ with $i\neq j$. So to conclude that
$\frac{\mathbb{E}\left[I^{2}_{n}\right]}{\mathbb{E}\left[I_{d}\right]^{2}}\underset{n\to\infty}{\longrightarrow}1$,
it suffices to show that for any $\varepsilon>0$ and $n$ large enough,

$\mathbb{P}\left(U_{i,d}=2\right)\mathbb{P}\left(U_{j,d}=2\right)\geq(1-\varepsilon)\mathbb{P}\left(U_{i,d}=2,U_{j,d}=2\right),\leavevmode\nobreak\
\forall i\neq j\in[k_{n}].$ (B.19)

Now, given $\delta>0$,

$\begin{split}\mathbb{P}\left(U_{i,d}=2\right)\mathbb{P}\left(U_{j,d}=2\right)&=\mathbb{E}\left[\binom{N}{2}p^{2}_{i,d}(1-p_{i,d})^{N-2}\right]\mathbb{E}\left[\binom{N}{2}p^{2}_{j,d}(1-p_{j,d})^{N-2}\right]\\\
&\geq\mathbb{P}\left(|N-qn|<\delta
qn\right)^{2}\binom{(1-\delta)qn}{2}^{2}p^{2}_{i,d}p^{2}_{j,d}(1-p_{i,d})^{(1+\delta)qn}(1-p_{j,d})^{(1+\delta)qn},\end{split}$
(B.20)

and,

$\begin{split}\mathbb{P}\left(U_{i,d}=2,U_{j,d}=2\right)&=\mathbb{E}\left[\binom{N}{4}\binom{4}{2}p^{2}_{i,d}p^{2}_{j,d}(1-p_{i,d}-p_{j,d})^{N-4}\right]\\\
&\leq\mathbb{P}\left(|N-qn|<\delta
qn\right)\frac{(1+\delta)^{4}q^{4}n^{4}}{4}p^{2}_{i,d}p^{2}_{j,d}(1-p_{i,d}-p_{j,d})^{(1-\delta)qn-4}\\\
&+\mathbb{P}\left(|N-qn|\geq\delta qn\right).\end{split}$ (B.21)

Note that,

$\begin{split}\log\left(\frac{(1-p_{i,d}-p_{j,d})^{(1-\delta)qn-4}}{(1-p_{i,d})^{(1+\delta)qn-2}(1-p_{j,d})^{(1+\delta)qn-2}}\right)&=-qn\log\left(1+\frac{p_{i,d}p_{j,d}}{(1-p_{i,d}-p_{j,d})}\right)\\\
&-(\delta qn+4)\log\left(1-p_{i,d}-p_{j,d}\right)\\\ &-\delta
qn\log\left(1-p_{i,d}\right)\\\ &-\delta
qn\log\left(1-p_{j,d}\right).\end{split}$ (B.22)

For sufficiently large $n$, using our assumption that $r\leq l$,

$\begin{split}\left|qn\log\left(1+\frac{p_{i,d}p_{j,d}}{(1-p_{i,d}-p_{j,d})}\right)\right|&\leq
2qnp_{i,d}p_{j,d}\\\ &\leq 2qne^{2\beta
d}\left(\frac{r}{2R_{d}}\right)^{2d}\\\ &\leq
2qn\frac{1}{(n-1)^{2}}\underset{n\to\infty}{\longrightarrow}0.\end{split}$
(B.23)

Also, for sufficiently large $n$,

$|(\delta qn+4)\log\left(1-p_{i,d}-p_{j,d}\right)|\leq 2\delta
qn\left|\log\left(1-\frac{2}{(n-1)}\right)\right|\underset{n\to\infty}{\longrightarrow}4\delta
q.$ (B.24)

Since,

$(\delta qn+4)|\log\left(1-p_{i,d}-p_{j,d}\right)|\geq\delta
qn|\log\left(1-p_{i,d}\right)|\vee\delta qn|\log\left(1-p_{j,d}\right)|,$
(B.25)

it follows that,

$\limsup_{n\to+\infty}\left|\log\left(\frac{(1-p_{i,d}-p_{j,d})^{(1-\delta)qn-4}}{(1-p_{i,d})^{(1+\delta)qn-2}(1-p_{j,d})^{(1+\delta)qn-2}}\right)\right|\leq
12\delta q,$ (B.26)

thus taking $\delta>0$ sufficiently small, for all sufficiently large $n$,

$\frac{(1-p_{i,d})^{(1+\delta)qn}(1-p_{j,d})^{(1+\delta)qn}}{(1-p_{i,d}-p_{j,d})^{(1-\delta)qn-4}}\geq\left(1-\frac{\varepsilon}{2}\right).$
(B.27)

From this (B.19) follows taking $n$ large and $\delta$ smaller if necessary to
make the other factors of the ratio become closer to $1$. It follows that,

$\frac{\mathbb{E}\left[I^{2}_{n}\right]}{\mathbb{E}\left[I_{n}\right]^{2}}\underset{n\to\infty}{\longrightarrow}1,$
(B.28)

from which it follows that $I_{n}\geq\frac{\mathbb{E}\left[I_{n}\right]}{2}$
with high probability. Repeating the last part of the proof of Lemma 1.2 for
the case $r>l$, it follows that,

$|M_{r}|\geq\frac{\gamma^{2}}{32}e^{-d(3\beta+\log(8))}\left(n^{2}\left(\frac{r}{R_{d}}\right)^{d}\wedge
n\right)$ (B.29)

with high probability and thus the result follows.

∎

With the above results the proof of Theorem B.1 follows readily:

###### Proof of Theorem B.1.

The result follows by combining Lemma B.3 and Lemma B.4by taking
$r=R_{d}\sigma$. ∎

###  B.2 Information theoretic results

In this subsection we give the following positive probability analogue of
Theorem 1.1:

######  Theorem B.5 (Positive probability lower bound).

Assume that for each $n$, LD in (1.1) holds for some
$R_{d},\|\,\cdot\,\|,\gamma$ and $\beta$ with $\gamma$ and $\beta$ that do not
depend on $n$. If $e^{-10\beta d}\sigma^{d}n^{2}\to+\infty$, then as
$n\to+\infty$,

$\inf_{\hat{\pi}}\mathbb{P}\left(d_{H}\left({\hat{\pi}},{\pi^{*}}\right)\geq\frac{\gamma^{2}}{128}e^{-7\beta
d}\left((n^{2}\sigma^{d})\wedge n\right)\right)\geq\frac{(1-o(1))}{8},$ (B.30)

where the infimum above is taken over all estimators $\hat{\pi}$.

This result in particular completes the picture given by Theorem 3 in [24] for
$d=o(\log n)$ and generalizes their conclusions when $d$ is fixed for a wider
class of distributions:

######  Corollary B.6.

Given the assumptions of Theorem B.5 and $d=o(\log n)$, for any estimator
$\hat{\pi}$ and $\alpha\in[0,1)$, if

$d_{H}\left({\hat{\pi}},{\pi^{\star}}\right)=o(n^{\alpha})\text{ with high
probability},$ (B.31)

then,

$\sigma=o\left(n^{\frac{\alpha-2}{d}}\right).$ (B.32)

If we assume additionally that $d$ is fixed, the result also holds for
$\alpha=1$.

###### Proof.

$d_{H}\left({\hat{\pi}},{\pi^{\star}}\right)=o(n^{\alpha})$ with high
probability implies that,

$\mathbb{P}\left(d_{H}\left({\hat{\pi}},{\pi^{\star}}\right)\leq
n^{\alpha}\right)\underset{n\to\infty}{\longrightarrow}1.$ (B.33)

But then from our lower bound in Theorem B.5,

$n^{\alpha}\geq\frac{\gamma^{2}}{128}e^{-7\beta
d}\left((n^{2}\sigma^{d})\wedge n\right),$ (B.34)

for sufficiently large $n$. Since $e^{-7\beta d}n=n^{1-o(1)}>n^{\alpha}$ for
sufficiently large $n$, this implies that,

$n^{\alpha}\geq\frac{\gamma^{2}}{128}e^{-7\beta d}n^{2}\sigma^{d},$ (B.35)

and thus,

$\sigma=o\left(n^{\frac{\alpha-2}{d}}\right),$ (B.36)

as claimed. If we assume that $d$ is fixed and
$d_{H}\left({\hat{\pi}},{\pi^{\star}}\right)=o(n)$ with high probability, then
for any $\varepsilon>0$,

$\mathbb{P}\left(d_{H}\left({\hat{\pi}},{\pi^{\star}}\right)<\varepsilon\frac{\gamma^{2}}{128}e^{-7\beta
d}n\right)\underset{n\to\infty}{\longrightarrow}1$ (B.37)

and in particular we must have:

$\varepsilon n\geq n^{2}\sigma^{d},$ (B.38)

which implies $\sigma=o(n^{-\frac{1}{d}})$. ∎

In order to prove Theorem B.5 we prove the following analogue of Lemma 3.1:

######  Lemma B.7 (Positive probability lower bound on
$d_{H}\left({\hat{\pi}},{\pi^{\star}}\right)$).

Given the same setting as Lemma 3.1, if
$|M_{r}|t_{\frac{r}{\sigma}}(\mathcal{Q})\geq 8$, then for any estimator
$\hat{\pi}=\hat{\pi}(x_{1},\dots,x_{n},Y_{1},\dots,Y_{n})\in S_{n}$,

$\mathbb{P}\left(d_{H}\left({\hat{\pi}},{\pi^{\star}}\right)\geq\frac{|M_{r}|t_{\frac{r}{\sigma}}(\mathcal{Q})}{4}\right)\geq\frac{1}{8},$
(B.39)

for $t_{s}(\mathcal{Q})$ as in (3.3) and
$M_{r}=M_{r}(\\{x_{1},\dots,x_{n}\\})$ the largest matching in
$G(\\{x_{1},\dots,x_{n}\\},r,d,\|\,\cdot\,\|)$.

###### Proof.

Assume once again for ease of notation that
$M_{r}=\\{\\{2j-1,2j\\}\\}_{j=1}^{m}$ and let $\mathcal{Q}(v,\sigma)$ denote
the law of $v+\sigma\tilde{Z}$, $\tilde{Z}\sim\mathcal{Q}$. Note that given
$P$ and $Q$ two measures on $(\mathbb{R}^{d})^{2}$,

$\left\|{P-Q}\right\|_{TV}=\inf_{(W^{(0)},W^{(1)})}\mathbb{P}\left(W^{(0)}\neq
W^{(1)}\right),$ (B.40)

where the infimum is taken over all pairs $(W^{(0)},W^{(1)})$ such that
$W^{(0)}\sim P$ and $W^{(1)}\sim Q$. Following [23] Theorem 4.1 we have that
for any pair $x_{2j-1},x_{2j}\in\mathbb{R}^{d}$ there exists an optimal
coupling $(W^{(0)},W^{(1)})$ in
$(\mathbb{R}^{d})^{2}\times(\mathbb{R}^{d})^{2}$ with,

$W^{(0)}\sim Q(x_{2j-1},\sigma)\otimes Q(x_{2j},\sigma)\text{ and }W^{(1)}\sim
Q(x_{2j},\sigma)\otimes Q(x_{2j-1},\sigma)$ (B.41)

such that,

$\mathbb{P}\left(W^{(0)}=W^{(1)}\right)=1-\left\|{Q(x_{2j-1},\sigma)\otimes
Q(x_{2j},\sigma)-Q(x_{2j},\sigma)\otimes
Q(x_{2j-1},\sigma)}\right\|_{TV}=:p_{j}.$ (B.42)

Note that from (3.12) we know that for all $j\in[m]$,

$p_{j}\geq t_{\frac{r}{\sigma}}(\mathcal{Q}).$ (B.43)

Let $\\{(W^{(0)}_{j},W^{(1)}_{j})\\}_{j=1}^{m}$ be independent optimal
couplings of the respective collection of pairs of laws,

$\\{\left(Q(x_{2j-1},\sigma)\otimes Q(x_{2j},\sigma),Q(x_{2j},\sigma)\otimes
Q(x_{2j-1},\sigma)\right)\\}_{j=1}^{m}.$ (B.44)

Let $C_{j}$ be the indicator of the event $W^{(0)}_{j}=W^{(1)}_{j}$. We define
$b$ and $b^{\prime}$ two random elements of $\\{0,1\\}^{m}$ by doing the
following procedure independently for each $j\in[m]$:

  1. (i)

$b_{j},b^{\prime}_{j}\stackrel{{\scriptstyle\text{iid}}}{{\sim}}\text{Unif}(\\{0,1\\})$
if $C_{j}=1$,

  2. (ii)

$b_{j}\sim\text{Unif}(\\{0,1\\})$ and $b^{\prime}_{j}=b_{j}$ if $C_{j}=0$.

The key aspect of this construction is that although the joint pair
$(b_{j},b_{j}^{\prime})$ depends on $C_{j}$, taken individually, both $b_{j}$
and $b^{\prime}_{j}$ have the same marginal distribution and are each
independent of $C_{j}$, and thus from $W_{j}^{(0)},W_{j}^{(1)}$. Let
$\tilde{Z}_{1},\dots,\tilde{Z}_{n}\stackrel{{\scriptstyle\text{iid}}}{{\sim}}\mathcal{Q}$
be generated independently. Given $\omega\in\\{0,1\\}^{m}$ we define a
sequence of final positions $Y^{(\omega)}_{1},\dots,Y^{(\omega)}_{n}$ by:

$(Y^{(\omega)}_{2j-1},Y^{(\omega)}_{2j})=W^{(\omega_{j})}_{j},\leavevmode\nobreak\
j\in[m],$ (B.45)

and,

$Y^{(\omega)}_{i}=x_{i}+\sigma\tilde{Z}_{i},\leavevmode\nobreak\
i=2m+1,\dots,n.$ (B.46)

Note that
$Y^{(b)}_{1},\dots,Y^{(b)}_{n}=Y^{(b^{\prime})}_{1},\dots,Y^{(b^{\prime})}_{n}$
by construction. Moreover, conditioned on $b=\omega$, since $b$ is independent
of the $W_{j}^{(0)}$’s and $W_{j}^{(1)}$’s,

$Y^{(b)}_{1},\dots,Y^{(b)}_{n}\sim\bigotimes_{i=1}^{n}\mathcal{Q}\left(x_{\pi_{\omega}(i)},\sigma\right),$
(B.47)

where $\pi_{\omega}=\prod_{j=1}((2j-1)2j)^{\omega_{j}}$. By symmetry the same
conclusion holds for $b^{\prime}$. Since
$b,b^{\prime}\sim\mathrm{Unif}\left(\\{0,1\\}^{m}\right)$ it follows that,

$(b,Y^{(b)}_{1},\dots,Y^{(b)}_{n})\stackrel{{\scriptstyle(d)}}{{=}}(b^{\prime},Y^{(b^{\prime})}_{1},\dots,Y^{(b^{\prime})}_{n}).$
(B.48)

Let $\pi^{*}\sim\mathrm{Unif}(S_{n})$ be sampled independently. Note that
conditioned on $b=\omega$ and $\pi^{*}=\pi$,

$Y^{(b)}_{\pi^{*}(1)},\dots,Y^{(b)}_{\pi^{*}(n)}\sim\bigotimes_{i=1}^{n}\mathcal{Q}\left(x_{(\pi_{\omega}\circ\pi)(i)},\sigma\right).$
(B.49)

Since
$\pi_{b}\circ\pi^{*},\pi_{b^{\prime}}\circ\pi^{*}\sim\mathrm{Unif}(S_{n})$, it
follows that,

$\begin{split}(\pi_{b}\circ\pi^{*},Y^{(b)}_{\pi^{*}(1)},\dots,Y^{(b)}_{\pi^{*}(n)})&\stackrel{{\scriptstyle(d)}}{{=}}(\pi_{b^{\prime}}\circ\pi^{*},Y^{(b^{\prime})}_{\pi^{*}(1)},\dots,Y^{(b^{\prime})}_{\pi^{*}(n)})\\\
&\stackrel{{\scriptstyle(d)}}{{=}}(\pi^{*},Y_{1},\dots,Y_{n}),\end{split}$
(B.50)

where $Y_{1},\dots,Y_{n}$ is defined by:

$Y_{i}=x_{\pi^{*}(i)}+\sigma\tilde{Z}_{i},\leavevmode\nobreak\ i\in[n].$
(B.51)

In particular, since
$\hat{\pi}(x_{1},\dots,x_{n},Y^{(b)}_{\pi^{*}(1)},\dots,Y^{(b)}_{\pi^{*}(n)})=\hat{\pi}(x_{1},\dots,x_{n},Y^{(b^{\prime})}_{\pi^{*}(1)},\dots,Y^{(b^{\prime})}_{\pi^{*}(n)})$,
setting,

$\hat{\pi}_{b}=\hat{\pi}(x_{1},\dots,x_{n},Y^{(b)}_{\pi^{*}(1)},\dots,Y^{(b)}_{\pi^{*}(n)}),$
(B.52)

for ease of notation, we have by the triangular inequality,

$\begin{split}d_{H}\left({\hat{\pi}_{b}},{\pi_{b}\circ\pi^{*}}\right)+d_{H}\left({\hat{\pi}_{b}},{\pi_{b^{\prime}}\circ\pi^{*}}\right)&\geq
d_{H}\left({\pi_{b}\circ\pi^{*}},{\pi_{b^{\prime}}\circ\pi^{*}}\right)\\\
&=2d_{H}\left({b^{\prime}},{b}\right).\end{split}$ (B.53)

Now, by a coupling argument using (B.43) and the independence of
$\\{(b_{j},b^{\prime}_{j})\\}_{j=1}^{m}$,

$d_{H}\left({b^{\prime}},{b}\right)\geq H,$ (B.54)

where $H\sim\mathrm{Binom}(m,\frac{1}{2}t_{\frac{r}{\sigma}}(\mathcal{Q}))$.
Since $|M_{r}|t_{\frac{r}{\sigma}}(\mathcal{Q})\geq 8$ using Chernoff’s
inequality,

$\mathbb{P}\left(H\geq\frac{t_{\frac{r}{\sigma}}(\mathcal{Q})|M_{r}|}{4}\right)=\mathbb{P}\left(H\geq\frac{\mathbb{E}\left[H\right]}{2}\right)\geq
1-e^{-\frac{1}{2}}\geq\frac{1}{4}.$ (B.55)

We thus have that:

$\begin{split}\mathbb{P}\left(d_{H}\left({\hat{\pi}_{b}},{\pi_{b}\circ\pi^{*}}\right)\geq\frac{t_{\frac{r}{\sigma}}(\mathcal{Q})|M_{r}|}{4}\right)+\mathbb{P}\left(d_{H}\left({\hat{\pi}_{b}},{\pi_{b^{\prime}}\circ\pi^{*}}\right)\geq\frac{t_{\frac{r}{\sigma}}(\mathcal{Q})|M_{r}|}{4}\right)&\geq\mathbb{P}\left(d_{H}\left({b^{\prime}},{b}\right)\geq\frac{t_{\frac{r}{\sigma}}(\mathcal{Q})|M_{r}|}{4}\right)\\\
&\geq\mathbb{P}\left(H\geq\frac{t_{\frac{r}{\sigma}}(\mathcal{Q})|M_{r}|}{4}\right)\\\
&\geq\frac{1}{4}.\end{split}$ (B.56)

Note that,

$\begin{split}d_{H}\left({\hat{\pi}(x_{1},\dots,x_{n},Y^{(b)}_{1},\dots,Y^{(b)}_{n})},{\pi_{b}\circ\pi^{*}}\right)&\stackrel{{\scriptstyle(d)}}{{=}}d_{H}\left({\hat{\pi}(x_{1},\dots,x_{n},Y_{1},\dots,Y_{n})},{\pi^{*}}\right)\\\
&\stackrel{{\scriptstyle(d)}}{{=}}d_{H}\left({\hat{\pi}(x_{1},\dots,x_{n},Y^{(b^{\prime})}_{1},\dots,Y^{(b^{\prime})}_{n})},{\pi_{b^{\prime}}\circ\pi^{*}}\right)\end{split}$
(B.57)

and so,

$\mathbb{P}\left(d_{H}\left({\hat{\pi}(x_{1},\dots,x_{n},Y_{1},\dots,Y_{n})},{\pi^{*}}\right)\geq\frac{t_{\frac{r}{\sigma}}(\mathcal{Q})|M_{r}|}{4}\right)\geq\frac{1}{8},$
(B.58)

as desired.

∎

We are now in position to prove Theorem B.5:

###### Proof of Theorem B.5.

Just combine Lemma B.7 and Lemma B.4 taking $r=R_{d}\sigma$. ∎

##  Appendix C Recovering lower bounds for the logarithmic regime in the
Gaussian model

In this section we show that if 5.3 holds, then we can use Lemma B.3 to
recover the lower bound from [11] on the logarithmic regime for some choices
of $a>0$ and $\sigma^{2}>0$.

We assume the Gaussian model from [11], i.e.
$\mathcal{P}=\mathcal{N}(0,I_{d})$ and
$\mathcal{Q}=\mathcal{N}(0,\sigma^{2}I_{d})$ in (1.1), and the logarithmic
regime i.e. $d=a\log n$. For the Gaussian model we have:

$q_{\frac{r}{\sigma}}(\mathcal{Q})=\left(1-\Phi\left(\frac{r}{\sqrt{2}\sigma}\right)\right),$
(C.1)

where $\Phi$ is the cumulative distribution function of a standard Gaussian
random variable. Let,

$I(t)=\frac{1}{2}\left(t-1-\log\left(t\right)\right)\text{ for }t>0$ (C.2)

be the large deviation rate function of a chi-squared random variable with $1$
degree of freedom. For a fixed $\sigma^{2}>0$ consider $r^{2}=\gamma d$ for
some $\gamma\in(0,2)$. Letting
$G(n,r,d)=G(n,r,d,\left\|{\,\cdot\,}\right\|_{2})$ be the random geometric
graph induced by joining initial positions within Euclidean distance $r$, we
have that:

$\displaystyle\log\left(\mathbb{E}\left[E(G(n,r,d))\right]\left(1-\Phi\left(\frac{r}{\sqrt{2}\sigma}\right)\right)\right)$
$\displaystyle=\log\left(\binom{n}{2}\right)+\log\left(\mathbb{P}\left(\|X_{1}-X_{2}\|_{2}^{2}\leq\gamma
d\right)\right)+\log\left(1-\Phi\left(\frac{\sqrt{\gamma
d}}{\sqrt{2}\sigma}\right)\right).$

Dividing all terms by $\log n$, taking the limit as $n\to\infty$, and using
that $d=a\log n$,

$\displaystyle\lim_{n\to+\infty}\frac{\log\left(\mathbb{E}\left[E(G(n,r,d))\right]\left(1-\Phi\left(\frac{r}{\sqrt{2}\sigma}\right)\right)\right)}{\log
n}$
$\displaystyle=2-aI\left(\frac{\gamma}{2}\right)-\frac{a\gamma}{4\sigma^{2}}$
(C.3)
$\displaystyle=2-\frac{a}{2}\left(2I\left(\frac{\gamma}{2}\right)+\frac{\gamma}{2\sigma^{2}}\right)$
(C.4)
$\displaystyle=2-\frac{a}{2}\left(\frac{\gamma}{2}\left(1+\frac{1}{\sigma^{2}}\right)-1-\log\left(\frac{\gamma}{2}\right)\right).$
(C.5)

The last expression is maximized by taking
$\gamma^{*}=2\left(1+\frac{1}{\sigma^{2}}\right)^{-1}$ which gives a value of
$2-\frac{a}{2}\log\left(1+\frac{1}{\sigma^{2}}\right)$, precisely the rate
established in [11]. Let $r^{*}=\sqrt{\gamma^{*}d}$. If we assume 5.3 then
$|M_{r^{*}}|=\Theta\left(\mathbb{E}\left[E(G(n,r^{*},d))\right]\wedge
n\right)$ with high probability, from which it follows that:

$\frac{\log\left(|M_{r^{*}}|\right)}{\log\left(\mathbb{E}\left[E(G(n,r^{*},d))\right]\wedge
n\right)}\overset{(\mathbb{P})}{\underset{n\to\infty}{\longrightarrow}}1,$
(C.6)

since $\mathbb{E}\left[E(G(n,r^{*},d))\right]\to+\infty$. In particular, if
$1\ll\mathbb{E}\left[E(G(n,r^{*},d))\right]\ll n$, then by Lemma B.3, we have
with high probability that,

$\begin{split}\frac{\log\left(d_{H}\left({\hat{\pi}_{\mathrm{LSS}}},{\pi^{\star}}\right)\vee
1\right)}{\log\left(n\right)}\geq\frac{\log\left(|M_{r^{*}}|q_{\frac{r^{*}}{\sigma}}\right)-\log(2)}{\log
n}.\end{split}$ (C.7)

Since the last expression converges to
$2-\frac{a}{2}\log\left(1+\frac{1}{\sigma^{2}}\right)$ in probability we have
that,

$d_{H}\left({\hat{\pi}_{\mathrm{LSS}}},{\pi^{\star}}\right)\vee 1\geq
n^{\alpha+o_{p}(1)},$ (C.8)

where $\alpha=2-\frac{a}{2}\log\left(1+\frac{1}{\sigma^{2}}\right)$.

Unfortunately the additional constraint that
$1\ll\mathbb{E}\left[E(G(n,r^{*},d))\right]\ll n$ implies that
$2-aI\left(\frac{\gamma^{*}}{2}\right)\in(0,1)$ and so in (C.8) we have an
additional constraint on $a>0$ and $\sigma^{2}>0$. Moreover, similar to [11]
we are unable to establish a lower bound of order $\Omega(n)$ with this
strategy, as it also only deals with augmenting cycles of size $2$.