Aligning Embeddings and Geometric Random Graphs: Informational Results and Computational Approaches for the Procrustes-Wasserstein Problem
Authors: Mathieu Even
Luca Ganassali
Jakob Maier
Laurent Massoulié
Venue: NeurIPS 2024 poster (2024)
Keywords: unsupervised learning
alignment of embeddings
high dimensional statistics
Primary area: learning_theory
TL;DR: We provide information-theoretic and computational results for the unsupervised  matching two high-dimensional point clouds.

Abstract: The Procrustes-Wasserstein problem consists in matching two high-dimensional point clouds in an unsupervised setting, and has many applications in natural language processing and computer vision. 
We consider a planted model with two datasets $X,Y$ that consist of $n$ datapoints in $\mathbb{R}^d$, where $Y$ is a noisy version of $X$, up to an orthogonal transformation and a relabeling of the data points. 
This setting is related to the graph alignment problem in geometric models.
In this work, we focus on the euclidean transport cost between the point clouds as a measure of performance for the alignment. We first establish information-theoretic results, in the high ($d \gg \log n$) and low ($d \ll \log n$) dimensional regimes. 
We then study computational aspects and propose the ‘Ping-Pong algorithm', alternatively estimating the orthogonal transformation and the relabeling, initialized via a Franke-Wolfe convex relaxation. We give sufficient conditions for the method to retrieve the planted signal after one single step. We provide experimental results to compare the proposed approach with the state-of-the-art method of Grave et al. (2019).

Aligning Embeddings and Geometric Random Graphs: Informational Results and Computational Approaches for the Procrustes- Wasserstein Problem
Mathieu Even
Luca Ganassali Université Paris-Saclay, LMO
DI ENS, CRNS, PSL University, INRIA Paris
Jakob Maier
D.I ENS, CRNS, PSL University, INRIA Paris
Laurent Massoulié
D.I ENS, CRNS, PSL University, INRIA, MSR-INRIA Joint Centre, Paris
Abstract
The Bpocustes-Wasseessiee problem consists in matching two high-dimensional point clouds in an unsupervised setting, and has many applications in natural language processing and computer vision. We consider a planted model with two datasets X, Y that consist of datapoints in Rd, where Y is noisy version of X, up to an orthogonal transformation and a relabeling of the data points. This setting is related to the graph aligmment problem in geometric models. In this work, we focus on the euclidean transport cost between the point clouds as a measure of performance for the alignment. We first establish information theoretic results, in the high (d >> log n) and low (d < log n) dimensional regimes. We then study computational aspects and propose the 'Ping-Pong algorithm', alternatively estimating the orthogonal transformation and the relabeling, initialized via a Franke- Wolfe convex relaxation. We give sufficient conditions for the method to retrieve the planted signal after one single step. We provide experimental results to compare the proposed approach with the state-of-the-ee method of Grave et al. 2019
Introduction
Finding an alignment between high dimensional vectors across two point clouds of embeddings has been the focus of recent threads of research and has a variety of applications in computer vision, such inferring scene geometry and camera motion from a stream of images [Tomasi and Kanade 1992 as well as in natural language processing such as automatic unsupervised translation [Rapp 1995
Fung 1995].
Many practical algorithms proposed for this task view this problem as minimizing the distance across distributions in Rdd Some approaches are based e.g. on optimal transport and Gromov- Wasserstein
distance Alvarez-Melis and Jaakkola| [2018] or adversarial lcarning [Zhang al. 2017 Conneau et al. 2018). Another line of methods adapt the iterative closest points procedure (ICP) originally introduced in Besl and McKay [1992] for 3-D shapes
higher dimensions Hoshen and Wolf
[2018]. Another recent contribution is that of Grave et al. [2019). where method is proposed to
jointly learn an orthogonal transformation and an alignment between two point clouds by alternating the objectives in the corresponding minimization problem.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

To formalize this problem, we consider Gaussian model in which both datasets X.Y E d (or two point clouds of n datapoints in R4) are sampled as follows. First, X (I)...., .n) is collection of i.i.d. (0, Id) Gaussian vectors, and Y = (V1,..., Un) ) is noisy version of X = (#1,...., Fn), up to an orthogonal transformation Q* and relabeling x' [n]] + [m] of the data points, that is:
Vi E [m], yi = ==" + t2i,
(1)
or, in matrix form:
Y= Q=X((P") =ZZ,
where Z (21,..., 2n) E Rddx also made of i.idd .V I2) Gaussian vectors, P* is the permuta- tion matrix associated with some permutation nT, and Ø > 0 is the noise parameter. Recovering (in some sense that will be made precise in the sequel) the (unknown) permutation ' and orthogonal transformation Q" defines the Procrustes- Wasserstein problem (sometimes abbreviated as PW in the sequel), which will be the focus of this study.
The practical approaches previously mentioned have shown good empirical results and are often scalable to large datasets. However, they suffer from lack of theoretical results to guarantee their performance or to exhibit regimes where they fail. Model (Ι) described here above appears to be the simplest one obtain such guarantees. We interested in pinning down the fundamental limits of the Procrustes- Waaiiess-ssssseeinn problem, hence providing an ideal baseline for any computational method be compared to, before delving into computational aspects. Our contributions are follows:
(1) We define a planted model for the Procrustes- Wassertein problem and discuss the appropriate choice of metrics to measure the performance of any estimator. Based on these metrics, e
(i.a) information-theoreiie results in the high-dimensional d >> log n regime which not explored before for this problem;
(i.b) new information-theoreiic results in the low-dimensional regime (d << log n) for our metric of performance (the L transport cost), which substantially differ from those obtained in Wang al. [2022] for the overlap.
We study computational aspects and propose the 'Ping-Pong algorithm', alternatively es- timating the orthogonal transformation and the relabeling. initialized via a Franke-Wolfe convex relaxation. This method is quite close to that proposed in Grave et al. (2019) although the alternating part differs. We give sufficient conditions for the method to retrieve the planted signal after one single step.
(iii) Finally, we provide experimental results to compare the proposed approach with the state- of-the-art method of Grave et al. 2019].
1.1 Discussion and related work
One can check that under the above model (. the maximum likelihood (ML) estimators of (P*, Q*) given (X, Y) is given by:
(P, E mig -
- Q TIP
arg min x0(d))
|QX - YPI
(P.Q)ES.
which is strictly equivalen to the formulation of the non-planted problem of Grave et al. 2019 Exactly solving the joint optimization problem (2) is non convex and difficult in general. However, if pa is known then (2) boils down to the following orthogonal Procrustes problem:
Q E arg min QEO(d)
|XP= Q Y
(3)
which has a simple closed form solution given by Q UVT where USV T is the singular value decomposition (SVD) of Y (X T (see Schönemann (1966)). Conversely, when Q* known, (
amounts to the following linear assignment problem (LAP in the sequel):
-|X Q- mag PES,,
(XPT QYY),
arg min PES,
'his very dichotomy (d > log n versus & log n) fundamental high dimensional statistics and not a mere artifact of our rationale; see Remark their matrices X and Y are the transposed versions of

---

Reference
Setting
Metries
Regime
Condition
for ov =
Kunisky and
a log
< n 1/4 forov(f, x ]= o[1]
Aules- Weed
Q' La
ov for p
d < (e - 1) for (v(f)x*)==
2022
d log n
- ((2e
((2e 1/-
(f)
d > log
0 < (1/2 [c/l//oo///0
for
Wane et al.
A X.
ov for P et for P". e for Q*
d log
a x 272 for ov(
d & n for ov ==)== o(1)
d & log
< d d for o (()
This paper
X. Y from
d 2 log
a & for for (f, a²) (Q, a(d)
Table 1:
Summary of previous informational results, together with the ones in this paper
which can be solved in polynomial time, e.g. in cubic time by the celebrated Hungarian algorithm [Kuhn 1955]. or more efficiently the price of regularizing the objective and using the celebrated Sinkhorn algorithm Cuturi 2013).
Previous results when Q* is known. As seen above, when Q* is known (assume e.g. Q" = Ia), the Procrustes- Wasserstein problem reduces to simpler objective, that of aligning Gaussian databases. This problem has been studied by Dai et al. (2019] 2023] in the context of feature matching, Kunisky and Niles- Weed [2022] study the same problem as a geometric extension of planted matching and establish -fce---attherttttt statistical bounds in the Gaussian model in the low-dimensional (d < logn), n), logarithmic (d ~ a log r)) and high-dimensional (d >> log r1) regimes. In particular, they show that exact recovery is feasible in the logarithmic regime d a log n. if o² < - and d log Note that in this problem, there is no
in the high-dimensional regime if o² < (1/4 E) computationaalstaaistiial gap since the LAP is always solvable in polynomial time.
Geometric graph alignment. Strongly connected to the Procrustes- Wassertein problem is the topic of graph alignment where the instances come from a geometric model. Wang et al. [2022] investigate this problem for complete weighted graphs. In their setting, given permutation '²" on [n|] and ii.d. pairs of correlated Gaussian vectors (Xx-(1) Y,) in RRd with noise parameter they observe matrices A XT X and B Y (i.e all inner products (X,, Xj) and (Y, Yj)) and are interested in recovering the hidden vertex correspondence n². The maximum likelihood estimator in this setting
writes
1 1 I PY 1 = arg max (PT x xP,YTT), PES.
arg min PES,
(5)
which is an instance of the quadratic assignment problem (QAP in the sequel), known to be NP-hard in general, as well as some of its approximations [Makarychev et al., 2014). In fact, we have the following informal equivalence (see Appendix A for proof):
Lemma 1 (Informal). PW and geometric graph alignement are equivalent, that is, one knows how to (approximately) solve the former iff they know how to (approximately) solve the latter.
Wang et al. 2022 focus on the low-dimensional regime d = o(logn), n), where geometry plays the most important role (see Remark [T] They prove that exact (resp. almost exact) recovery of r is possible as soon as o o(n 2/d) (resp. == o(n (1//m) They conduct numerical experiments which suggest good performance of the celebrated Umeyama algorithm (Umeyamal 1988), which is confirmed by a follow-up work by Gyng and Li (2024) analyzing the Umeyama algorithm (which is polynomial time in the low dimensional regime d o(log n)) in the same setting and shows that it achieves exact (resp. almost exact) recovery of n if a o(d-3n
cnoematiion-hhoretiiin
(resp. σ = o(d-3n -(/d), hence coinciding with the information thresholds up to a poly(d) factor. However, their algorithm is of time complexity at least 2(2d)))), which is not polynomial in This why we do not include this method in our baselines.
We emphasize that our results clearly depart from those obtained in Wang et al. 2022 and Gong and Li [2224), because (i) we are also interested in the high dimensional case d' log 71, and (ti) we work with a different performance metric which provides less stringent conditions for the recovery to be feasible, Section [.2] A summary of previous informational results together with ours (see also Section is given in Table
On the orthogonal transformation Q*. Generalizing the standard linear assignment problem, our model described above (T) introduces an additional orthogonal transformation Q' across the datascts. This orthogonal transformation can be motivated in the context of aligning embeddings in
3

---

high- sigh-dimensional space: indeed, the task of learning embeddings is often agnostic to orientation in the latent space. In other words, two point clouds may represent the same data points while having different global orientations. Hence, across different data sets, learning this orientation shift is crucial in order to compare (or align) the point clouds. As an illustration of this fact, Xing et al. [2015) provides empirical evidence that orthogonal transformations are particularly adapted for bilingual word translation.
Discussing the method proposed in Grave et al. 2079g. We conclude this introduction by discussing the work of Grave et al. [2019]. Their proposed algorithm is as follows. At each iteration t. given a current estimate Q2 of the orthogonal transformation, we sample mini-batcher Xx, Yú of same size b and find the optimal matching P. between Y and X,, via solving a linear assignment problem of size b. This matching P. in turn helps to refine the estimation of the orthogonal transformation via a projected gradient descent step, and the procedure repeats. This method has the main advantage to he scalable to very large datasets and to perform well in practice: however, no guarantees are given for this method, and in particular the mini-batch step which can justifiably raise some concerns. Indeed, since X, = )e(()) and Y, (Jt.)))E(b) are chosen independently, if 6 < vn it is likely that for any matching 5e the pairs {are.j ()) ) always correspond to disjoint pairs, and thus aligning Y.Q, and X2 does not reveal any useful information about the true P this is even more striking when the data is non-isotropic.
1.2 Problem setting and metrics of performance
Notations. We denote by X ~ NN,, Σ) with j E Rd and Σ E Rddd the fact that X follows a Gaussian distribution in Rd of mean fı and covariance matrix E. If f and Σ la- variable X is called standard Gaussian. We denote by (d) the orthogonal group in dimension d, and by S, the group of permutations on [mi] Throughout, || and (-) are is the standard euclidean norm and scalar product on Rd and -I- and || |lop are respectively the Frobenius matrix norm and the operator matrix norm. The spectral radius of a matrix A is denoted p(A). In all the proofs, quantities where i an integer are unspecified constants which are universal, that is independent from the parameters. Finally, all considered asymptotics are when n + cc. Note that d also depends on n. An event is said to hold with high probability (w..pp)) if its probability tends to 1 when n goes to co.
Problem setting and performance metrics. We work with the planted model as introduced in 1 and recall that our goal is to recover the permutation xt and the orthogonal matrix Q' from the observation of X and Y.
Performance metrics. Previous works measure the performance of an estimator स of a planted relabeling n² via the overlap:
1 Σ 1 (a)))) ov (T( = n i=1
(6)
defined for any two permutations ग. n'. This is an interesting metric when we have no hierarchy in the errors, that is when only the true match is valuable, and all wrong matches cost the same. However, this discrete measure does not take into account the underlying geometry of the model. A performance metric which is more adapted to our setting is the L transport cost between the point clouds. The natural intuition is that mismatch less costy if corresponds to embeddings which are in fact close in the underlying space. We define
(TT x')
Σ |00(0) xx000)
for any two permutations ग. T'. Note that this cost can also be written in matrix form as PP),-') = PP)xX') I|/-. From this form it is clear that, as stated before, c², P') is nothing but the euclidean transport cost for aligning X T onto X X(P)). Note that these two measures, ov and c², are also well-defined when P, P' are more general (and in particular when they are bistochastic matrices). Finally, we measure the performance for the estimation of Q* via the Frobenius norm:
L = 11Q Q'1
for the overlap, one could extend its definition using that ov P') PP.

---

defined for any two orthogonal matrices Q,Q'.
Comparison between metrics. For Haar-distributed matrix Q ((d), have that E (Q, (2,0") 2d, while for sampled uniformly from the set of all permutations, we have (ft ",,,TT π _²] = 2d(1 1 - 1/n) and E jov(f,, -²"] = 1/n. Hence, some estimators म. Q of x², Q* will perform well in our metrics they can achieve (Q, Q*) & ed, and c²(x,, T") < ed for some small (possibly vanishing) E 0.
Depending on dimension d, similarity measures given by c² and the overlap can behave differently or coincide. In the case where is small, and thus plays very important role, ov and e² have very different behaviors, and lead to very different results. particular, there a wide regime in which inferring x² for the overlap sense is impossible, but reachable in the transport cost sense, see Section
For any fixed permutation т. we have that E (T, TT]] taken with respect to the randomness of X. We also have the basic deterministic inequality
2d(1 - ov(TT=")),
x*)), where the mean is
( x
ov( x))) x
sup (6.))
||: - 2,
Thus, as long as (m)) || 2zl1? = Od). an estimator with good overlap (1 ov(n, m²) & e) also has good e² cost (c2 (n, x*) = ( However, this required control (u))))) ||x; zy (dd) only holds as long as d > log(n).
The blessing of large dimensions lead to an equivalence between the discrete metric ov, and the continuous transport metric o². We gather several important points highlighting the dichotomy between small and large dimensions for our problem in the following remark.
Remark 1. On the blessings of large dimensions for our problem:
1. For any open ball B of radius
O, denoting X' fx [n]]. have that IP (Bn 2) + 1 if >> log(n), while if d < log(n) then for all M > IP ((BnXX è M) + 1. In small dimensions, any fixed non-empty ball will contain infinitely many points of X as n increases, while in large dimensions these points are separated and any fixed ball will contain such points w.h.p.
2. For d >> log(n), matrix X/ dd satisfies the restricted isometry property (Candès 2008
3. For > log(n), the overlap and the transport cost metrics are equivalent: there ex- ist numerical constants a. >> 0) such that w.h.p., for all permutation matrices n, n², (T² & 2d(1 -v( x')) & (T,
Organization of the rest of the paper. Section 2 is dedicated to our informational results, giving their essential content as well as the main ideas on the proofs. We next discuss in Section some computational results, introducing the Ping-Pong algorithm, and presenting our numerical experiments.
Informational results
The substantial theoretic part of the paper stands in the informational results obtained for the Procrustes-Wee Wasserstein problem which we describe hereafter.
2.1 High dimensions
In the high-dimensional case when logn & d (and d log d & ni), our results Theorem I below imply that a + 0 then the ML estimators defined in (2) satisfy w.h.p.
ov(T" #) = 1- - o(1), c (')= = o(d), and e ( Q*) = o(d),
that is infer "* and Q" almost exactly, for all introduced metrics, soon as 0.
Note that this the first result the high-dimensional regime for the Procrustes Wassertein problem: Kunisky and Niles- Weed 2022 also considered this regime but only for the LAP problem (that
5

---

is recovering x² when Q" in known), and the only existing results for geometric graph alignment Wang et al. 2022], Gong and Li (2024) do not consider this high dimensional case. Our result thus complements the existing picture and shows that almost exact recovery is feasible under the loose assumption - 0, in the e² and the overlap sense, since these metrics are equivalent in large
dimensions (see Remark [). Our result is in fact more specific and only requires d > 2 2og We
prove the following Theorem:
Theorem 1. Assume that d 2 2log n.. There exists universal constants C1, 02, C3 that for large enough, with probability 1 o(1), the ML. estimators defined in satisfy
d
log
ov( , > max (60o²
C1 c C2 n
ddd2dlogg d
and
((Q",Q) 2d
d
log n
+ c20 + max < c1
(8)
The proof of Theorem iis detailed in Appendix C and builds upon controlling the probability of existence of certain subset of indices KCQQ, R. Q*) of vectors with prescribed properties in order to show that x can be recovered. We apply standard concentration inequalities to control the previous probability. The d > 2 llg((n) assumption is crucial here since it allows the union bound over S, to work.
2.2 Low dimensions
In the low-dimensional case when d < logn, Theorem 2 below implies that if - o(d-1/2) then there exist estimators n., Q that satisfy w.h.p.
P*)==(d)) and that is, one can approximate x' (in the e² sense only) and Q' as soon as a = o(d-1/2) This is of course to be put in contrast with the previous results on geometric graph alignment in this low- dimensional regime: for almost exact recovery in Wang et al. 2022 in the overlap sense, we need =(n l/d), which is far more restrictive than o = o(d 172 as soon as d log(d) < log that is nearly the whole low dimensional regime when d < log n. particular, since the rates of Wang et al. 2022) are sharp when d is of constant order, in order to approximate x² in the overlap sense it is necessary to have a to decreasing polynomially (at rate 1/d to O, whereas approximating π in the transport cost sense requires only o(1).
o(d),
There no contradiction here, since we recall that the c² metric and the overlap are not equivalent in small dimensions: let us give a few more insights on this. This scaling -1/d comes from the fact that in small dimensions, points of the dataset
close to each other, and the order of magnitude between some and its closest point in the dataset scales exactly n -1/dd, if the noise is smaller than this quantity, one should be able to recover the planted permutation. However, when comes to considering the e² metric, matching with j such that ||>, 1r,1 < that recovering a permutation with small c² cost and recovering Q* with small Frobenius norm error should be achievable even with large (i.e., that does no tend to 0 as n increases).
sufficient, thus suggesting
Our main theorem for low dimensions is follows.
Theorem 2. Let dg E (0, 1). There exist estimators â. Q xf Q* such that for some numerical constants C1. C2 > 0 we have a < C2d5d-112 and log(n) > C2dlog(1/8u), then:
2 2 ())
80 and e ((Q,Q))
< 60
2d
2d
refined version of Theorem 2 namely Theorem is proved in Appendix D We emphasize that the estimators considered in Theorem 2 are not the ML estimators: recall that the strategy to analyse the former as rolled out for Theorem T required the union bound over S, to work. This drastically fails when d & log(n). Hence, we will instead focus on an estimator that takes advantage of the fact that d small, and show that even in small dimensions, the signal-to-noise ratio does not need to decrease with n.

---

Let us first describe the intuition behind the estimators n. Q. When d = 1, Q-= = #1 and a simple strategy to recover Q* to count the number N (X). N_ (X)) (resp. N of positive and negative x; (resp. positive and negative fj): if N (2t) and (+)) are close, then we output
Q - +1, whereas if N (X) and ())) are close, then Q -1. In dimension d, an analog strategy can be applied at the cost of looking in all relevant directions, and the number of such directions exponentially big in d. Our strategy is thus follows. We compute the number of points that lie in given cone C(u, 8) of given angle 5 and direction Then, we estimate Q by the orthogonal transformation Q which makes the number of Vj in C(u, 6) closest to the number of Ty in C(Qu, 6), for any direction Note that this approach heavily relies the small dimension assumption d < log n:: in this case. for any constant ó, all theses cones contain w.h.p. large number of points (tending oo with n), which does not hold anymore when d > log n.
For 8 > and u E 5d-1, let C(u, 6) == {u E IR|| (u, v) B (1 (1- (1-5) be the cone of angle centered around u. Let = { E [n]]. 3 = {u,, [m]]. We now introduce the following sets, for some >> 0:
Cx(u, = X n n(u 8) B(0, 1/k) and Cy(u, y (nc
B(0, V1+ /1+02/K)) o²/m)C
where (0,,r) contains all vectors in Rd of norm larger than or equal to r. The role of k > 0 is to prevent side effects: indeed, since the cones are centered at the origin, points that too close to 0 fall into cones with arbitrary directions and are not informative for the statistics we want to compute.
Now, for some p > 1 and directions u1..... Up Sd-1 to be set later, we define the following conical alignment loss:
vQ E O(d), F(Q) = -
P (ICx(Qux, 8)1 [Cy(uu, 6)1)
1=1
The estimator Q in Theorem finite Net / C (dd):
2 is then defined as a minimizer of the conical alignment loss over
Q argmin F(Q),
QEN
where N will further be some e-net of (d), while á is then obtained by LAP as in (10).
2.3 From Pa to Q* and vice versa
In our proofs, we often prove that one of the estimators P or Q performs well in order to deduce that both perform well. This is thanks to the following two results, proved in Appendix B.] and B.2
Lemma 2 (From Q to P). Let 8 E (0, Assume that there exists Q that is
o(21,...,, V1, ... yn (n)))-maanee -measurable such that Partho ( exist constants C1, C22 C3 > such that with probability at least 2e -ed 2e -dp (V++
11 Q'112 & öd. There
Σ [+(() - QT
म E argmin TES.
yi
(10)
that can be computed in polynomial time (complexity O(n²)) )) as the solution of LAP, satisfies:
c² (²t
< G1 + C20² + + max d1In(1/8)
In(1/
d
7
Assume that there exists â that is o(f21..... .1...., Bn) measurabll such that (At, m²) öd. Let Q be the solution to the following optimization problem: There exist constants C1 Cz, Os > O such that with probability at least 1 - 2e -nd 2e (d² +n))
Lemma 3 (From P to Q). Let ā E (0.1/2).
Q
E arg min QEO(d) n
Σ ||0000 Q 1il
(11)
1=1
that can be computed in closed form with an SVD of XYT, satisfies:
(
d1n(1/8)
(n(1/))
< C15 C2o + max
d
n
n
7

---

Computational aspects
The estimators provided this far in Section 2 namely the joint minimization in P and Q in 2 and the minimizer of the conical alignment loss in ( are of course poly-time in general. In this section, we are interested in computational aspects of the problem.
3.1 Convex relaxation and Ping-Pong algorithm
Estimating P can be made via solving the QAP (5), that be convexified into the relaxed quadratic assignment problem (relaxed QAP):
Prelaxed E arg min
X -P-PP PYTY
(12)
PED,
where Dn is the polytope of bistochastic matrices, which is the convex envelope the set of permutation matrices. Note that unlike in (5) this argmin is not necessarily equal to arg maxpep. (PT X XP,YTY') since D, contains non-orthogonal matrices.
The estimate P Prelaxed gives a first estimate to then perform alternate minimizations in Q through an SVD - see (TT) and P through a LAP see (10). Combining an initialization with convex relaxation, computed via Frank- Frank-Wolfe algorithm (Jaggi 2013) and the alternate minimizations in P and Q yields the Ping-Pong algorithm.
Algorithm 1: PING-PONT ALGORITIIM
Input: Number of Frank Wolfe steps T, number of ditermate-minimiizzin steps K, Po 11
for k 0 to T 1 do
Compute S₁ = arg min (P, (P.))( (LAP), where -(P)= (xPP==XXXP_PPTX-
Pk+1 (1 - Pr S4 for 7k 24
Po = Pr and Qn Ia
for k = 10
do
Qu+1 V for YP,X V2 the SVD of Y Pk+1 E arg max (P.YTQK4zZ)) Qk+1X) (LAP)
(Ping)
(Pong)
Output: Pk. QK
Algorithm i structurally similar to Grave et al. 2019 's algorithm, explained in the introduction.
The difference lies in the steps in Lines 6-7 of Algorithm [ while Grave et al. [2019] perform projected gradient steps, approach is more greedy and directly minimizes in each variable. Both approaches are experimentally compared in Section
3.2 Guarantees for one step of Ping-Pong algorithm
Providing statistical rates for the outputs of Algorithm i challenging problem for two reasons. First, relaxed QAP is not well-understood problem: the only existing guarantees in the literature are for correlated Gaussian Wigner models in the noiseless case (i.e.,
in our model) (alldvvia and Tyagi 2023]. while for correlated Erdös- Rénnyi graphs, the relaxation is known to behave badly in general [Lzzinski al. 2016). Secondly, studying the iterates in lines 6 and of the algorithm is challenging, since these are projections on non non-convex sets. While Lemmas 2 and 3 show that if Pk (resp. Qx) has small e² loss, then QE+1 has small J loss (resp. P has small e loss), showing that there is a contraction at each iteration la Picard's 's fix-point Theorem' remains out of reach for this paper. We thus resort proving that one single step of Algorithm [ (K T 1) recover the planted signal, provided that the noise a is small enough.
Proposition 1. There exists C > 0 such that for any (0, if & n #, then the permutaatin associated to the outputs āt, Q of Algorithm 1 for = T = satisfies, with probability 1/n:
ov A, 8-8 8.
8

---

flod
Coneett p014
(a) varying d
(b) varying 72
Varying 10KZ) kadrandd
Vayting (2+12)) anddd
027
(c) varying a, small d
(d) varying a. large d
Figure 1: Influence of the parameters (dimensions d, number of points n. and noise level 0) on the accuracy (in terms of overlap) of three different estimators: the relaxed QAP estimator (12) projected the set of permutation matrices (blue curve), the output of Alg. [ (red curve). and the output of Grave et al. [2019] 's algorithm (purple curve). Each dot corresponds to averaging scores over 10 experiments. Figure La 0.34, n 100. Figure lb 0.34. d Figures Ic and ld 200, d = 2 and d = 60 respectively.
the nigh-damensional setting (d log(n)), there exist some constants C1 C2 such that if n then it satisfies w.h.p.
+1 (
dlog(d) +
log(n) log(d)
log(n)
( C2 max
d
d
Thus, for polynomially small in n and exponentially small in 1/8, one step of Alg. recovers н* in the overlap sense with error ò. In large dimensions, this is improved, since is no longer required be exponentially small as the target error decreases to zero. Proof of Proposition is given in Appendix
3.3 Numerical experiments
We compare in Figure our Alg. with (i) the naive initialization of the relaxed QAP estimator
(12). and (ii) the method in Grave et al. [2019]- The curve 'relaxed QAP via FW" is obtained by computing the relaxed QAP estimator with Trank-Wolfs algorithm with T 1000 steps, enough
for convergence. This estimator is then taken as initialization for Alg I and Grave et al. [2019] 's algorithm, that both taken with the same large number of steps (K 100, empirically leading to convergence to stationary points of the algorithms). For fair comparison, we take full batches in Grave 2019 (smaller batches lead even worse performances).
Conclusion
We establish new informational results for the Procrustes- Wassertein problem, both in the high (d >> 1) and low (d < logn) dimensional regimes. We propose the 'Ping-Pong algorithm', alternatively estimating the orthogonal transformation and the relabeling, initialized via a Franke- Wolfe convex relaxation. Our experimental results show that our method most globally outperforms the algorithm proposed in Grave et al. 2019

---

References
David Alvarez-Melis and Tommi Jaakkola. Gromov-Wass Wasserseein alignment of word embedding spaces. In Ellen Riloff, David Chiang. Julia Hockenmaier, and Jun an'ichi Tsujii, editors, Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 1881-1890, Brussels, Belgium, October-November 2018. Association for Computational Linguistics. doi: org/
10.18653/v1/DI 1-12 URL BtLLhtttps//aalaattoooooo
P.J. Besl and Neil D. McKay. A method for registration of 3-d shapes. IEEE Transactions Pattern Analysis and Machine Intelligence, 14(2):29-2266, 1992. doi: 10.1 109/14.911277
Emmanuel J. Candès. The restricted isometry property and its implications for compressed sensing.
Comptes Rendus Mathematique, 5469) 2008. ISSN 1631-073X. doi: htts://doi.org//0 1016/j.crma..200000 03.014. URLhttts::/wwez www.wwwwwwww.w.w........mm. http:///cc//cccceeeeariaiiilaaae $1631073X08000964
Alexis Conneau, Guillaume Lample, Marc' Aurelio Ranzato, Ludovic Denoyer, and Hervé Jégou.
Word translation without parallel data, 2018.
Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. In C.J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K.Q. Weinberger, editors, Advances Neural Information Processing Systems, volume 26. Curran Associates. Inc., 2013. URL
www.eeddiiinnnniusnne...o nwwripe..c..oeeooo www.rris.cccppp........ files wilee/ppaapaee htteee/iileee/pprr//11////////// pappp///01//fillee Paper pdf
Osman E. Dai, Daniel Cullina, and Negar Kiyavash. Database alignment with gaussian fea- tures. In Kamalika Chaudhuri and Masashi Sugiyama, editors, Proceedings of the Twenty- Second International Conference on Artificial Intelligence and Statistics, volume 89 of Pro- ceedings of Machine Learning Research, pages 3225-3233. PMLR, 16-18 Apr 2019. URL
https://proceedings mlr pross/v89/daiie html
Osman Emre Dai, Daniel Cullina, and Negar Kiyavash. Gaussian database alignment and gaussian planted matching, 2023.
Pascale Fung. Compiling bilingual lexicon entries from pan-lalllll English-Chinese corpus. In Third Workshop on Very Large Corpora, 1995. URL
Shuyang Gong and Zhangsong Li. The umeyama algorithm for matching correlated gaussian geometric models in the low-dimensional regime, 2024.
Edouard Grave, Armand Joulin, and Quentin Berthet. Unsupervised alignment of embeddings with wasserstein procrustes. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1880-1890. PMLR, 2019.
Yedid Hoshen and Lior Wolf. Non-adversarial unsupervised word translation, 2018.
Martin Jaggi. Revisiting Frank-Wolfe: Projection-free sparse convex optimization. In Sanjoy Dasgupta and David McAllester, editors, Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pages 427-435. Atlanta, Georgia, USA, 17-19 Jun 2013. PMLR. URL /ttpss:/pproceedingg mlr, www.prres.../eeee......em press/ htmml
v28 728/jaggi13 html
H. W. Kuhn.
The hungarian method for the assignment problem. Naval Research Logistics Quarterly. 2(1-2):83 97, 1955. doi: 7/onl conlinelibrary. wwwey. http//////bassooooee h000000000000
URL https
Dmitriy Kunisky and Jonathan Need. Strong recovery of geometric matchings, pages 834 876. 2022. doi: 10.1137/1..78161111 00 URL htttp::// siam. org/dol.
B. Laurent and P. Massart. Adaptive estimation of a quadratic functional by model selection. The Annals of Statistics, 28(5): 1302 - 1338, 2000. doi: 10.1214/2os/111599 URL. httpss
//doi orgo 10. 1214 000.o/////1/19991911
10

---

Vince Lyzinski, Donniell E. Fishkind, Marcelo Fiori, Joshua T. Vogelstein, Carey E. Priebe, and Guillermo Sapiro. Graph matching: Relax your own risk. IEEE Transactions Pattern Analysis and Machine Intelligence, 38(1):60-73, 2016. doi: 10.1 10.11999PMMM..21552224555
Konstantin Makarychev, Rajsekar Manokaran, and Maxim Sviridenko. Maximum quadratic as- signment problem: Reduction from maximum label cover and Ip-based approximation algorithm. ACM Trans. Algorithms, 10(4), aug 2014. ISSN 1549-6325. doi: 10.1145/2629672. URL
https://doi http:////oooorrg/1// 10. 0111111222267
Reinhard Rapp. Identifying word translations in non-parallel texts. In 33rd Annual Meeting of the Association for Computational Linguistics, pages 320-322, Cambridge, Massachusetts, USA, June 1995. Association for Computational Linguistics. doi: 10.31 1/9116589817799 URL
htttp://aclanthology oog. org/p95- 10///995110 1050
C. A. Rogers. Covering a sphere with spheres. Mathematikaa 10(2):157-164, 1963. doi: 10.1112/ $00255793000040883,
Peter Schönemann. A generalized solution of the orthogonal procrustes problem. Psychometrika, 31 (1):1-10, 1966. BRLl:tttt///cooaaapeer rewpc.eep........... werp:e..orrg/aeee.....pppooeooo.
1:1:p:1-10
Carlo Tomasi and Takeo Kanade. Shape and motion from image streams under orthography: factorization method. International Journal of Computer Vision, 132):137-154, Nov 1992. ISSN 1573-1405. doi: 10.1007/BF00129664 htthttts::/ddo..oo org/ 10. 1007 00.0000/000 BF001196601
S. Umeyama. An eigendeccopooitiinn approach weighted graph matching problems. IEEE Transactions on Pattern Analysis and Machine Intelligence, 10(5):955-703, 1988. doi: 10.1 10.1 34.6778.
Ernesto Araya Valdivia and Hemant Tyagi. Graph matching via convex relaxation to the simplex, 2023.
Roman Vershynin. Hiigh-Dimensione Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018. doi: 10.1017/978 108231596.
Haoyu Wang, Yihong Wu, Jiaming Xu, and Israel Yolou. Random graph matching in geometric models: the case of complete graphs. In Po-Ling Loh and Maxim Raginsky, editors, Proceedings Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 3441-3488. PMLR, 02-05 Jul 2022. URL/sttp::/prrceedngs mlr. c.resssss/
of Thirty Fifth Conference
v178/ 2/78/wang22... html htmml
Chao Xing, Dong Wang, Chao Liu, and Yiye Lin. Normalized word embedding and orthogonal transform for bilingual word translation. In Rada Mihalcea, Joyce Chai, and Anoop Sarkar, editors, Proceedings of the 2015 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 1006-1011, Denver, Colorado, May-June 2015. Association for Computational Linguistics. doi: 10.3115/v1/115-111 104. URL httts://accaattee
org/ N15- 1104
Meng Zhang, Yang Liu, Huanbo Luan, and Maosong Sun. Adversarial training for unsupervised bilingual lexicon induction. In Regina Barzilay and Min-Yer Kan, editors, Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics ( (Volume I: Long Papers), pages 1959-1970, Vancouver, Canada, July 2017. Association for Computational Linguistics. doi: 10.18653/v1/P17-1111 btpptttt://aacaathholooyg htw.://aannooooooooog-//11111111

---

A
Useful results
We start by proving Lemma 1 which gives the equivalence between PW and geometric graph alignement.
A.1 Proof of Lemma
Proof of Lemmal 7 We have by Lemma 3 that soon as we are able to estimate 't" with small error in PW, we are also capable of doing so Q², by perfoming a simple Singular Value Decomposition (SVD). Since one can trivially form an instance A = X X X and B Y of geometric graph alignement from an instance (X, Y) of PW from model ([, we can deduce that if we know how to (approximately) solve geometric graph alignement, we know how to (approximately) solve PW.
Conversely, if we are given adjacency matrices = X X, B = y of two correlated random geometric graphs under the Gaussian model from [Wang et al. 2022 Gong and Li 2024] where Vi = (x) + d2,, we can recover π via solving PW. Indeed, A is of rank at most d, so we can build X' = (a') leil...iate (a2,,) E Ædx= such that A X X'. Similarly, we can build Y = (víl.. ......l... W,) E Rdx= such that B = Y We have x = X"T X', hence (I,, = (o), ryy, thus there exists Q E (d) such that for all i E [n], x = Qiz;. Similarly, there exists Q2 E (d)) such that for all i, 1/4 - Qzys. By multiplying these two orthogonal matrices by independent random uniform orthogonal matrices, we can always assume that they are independent from X and Y. We obtained X", Y which satisfy y = =*===(00 + 02 for all i, where Q' Q2Q and z Qi 2 = Q2 are i.i.d. standard Gaussian vectors. This exactly an instance of the PW problem. If we know how to (approximately) solve the PW problem, we know how to (approximately) recover '' and thus (approximately) solve the geometric graph alignment problem.
This proves that PW and geometric graph alignement are equivalent.
A.2 n-nets of ((d)
Throughout the proofs, we will need to give high probability bounds on quantities for all orthogonal matrices. This done by covering (dd by a finite number of open balls centered at points of ((d).
This is done by considering E eent..
net of O(d) the Frobenius Definition 1 (c netnetsone of O(d)). Let >> O. A subset Nr C (dd) is a e
norm if for all O E (dd) there exists Oz E Ne such that |0 O=IIr & &.
Remark Note that since || 1-I1r & ||- llop by Cauchy-Schwee any e-net of (d) for the Frobenius norm is also an nenet of (d) for the operator norm.
We will need nete of (d) that are not too large, in order to apply union bounds which will give non-trivial probabilistic controls. Guarantees on such nets are standard in the literature; we give one which will be useful for us in the following Lemma.
Lemma 4 (e-nets of (dd of minimal size, see e.g. Rogers 1963 There exists universal
constant > 0 such that for all > 0, there exists an e e-net N. of O(d) such that
d
Cvd E
W& &
B Remaning proofs of Section 2
B.1 Proof of Lemma 2
Proof of Lemma 2 Denote g(T) == Σm [a(s) - -QT yi The proof relies on noticing that for
all Sn. by definition g(+) < ((T)) and using l|a + b112 >
a|ll
||b|22 one gets
g(+) 1 ( π) g(x).
1
12

---

and thus c²( r) & 4g(T). 2(1|a|1 + 1b]l2) one gets,
We apply the previous inequality to π x= and using l|a + bl]2 <
20
g( &
Σ/ i=1
(1a
Q)))
||
20
Q*)
where we used the fact that the matrices Q, Q" are orthogonal. Using concentration of Chi squared random variables, we have
P
Σ | > nd 2vnnt + 2t E
leading to Eh= ||
5nd)
< e nd by plugging in t = nd. We are now left with I= how-
E (Q- We have that for any Q, E Σ II( x=1]= n 1aalQ-QQ*11
ever, Q depends on the 2; so we need uniform upper bound. Using Hanson- Wrright inequality, for any Q Raxd
a
)) 20
IIQ - 0')=;11 nlIQ 11 emax (Vntlle-Q-li
Q*11² IQ @=I :1QQ Q- (116o)
which reads as, for Q orthogonal (leading to ||Q - 1op < 2):
IP Σ ((Q - )x,=11 nllQ Q²1 + max (aallQ-Q11: < 2t
For E E 1/2), let No be an E net of (dd) of minimal cardinality; by Lemma (og(
we have
& Cd In (dd/E).. Using union bound:
} 2 d' max (iulle-Qllia.)) <2e-ctCulludd/s)
P
sup QEN,
I(Q Q')=:11² n|lQ Q Σ
}
1=1
Taking t = A Cd2 (nd/e)) we have with probabiliy 2e-2 that:
Σ IIQ - Q*) |2,11 ml1Q - 12" < é' max (vettceeld/)))l000eee
Cd in(dfs) (n((//E)))
sup QEN.
Now, if Q, Q' (d) satisfy l|Q - Q''lp E, we have using the orthogonality property of these matrices:
- -')=01) Σ II( x²)=,11 =2 2 11Q' Qxx,2,)(''''0
1=1
n
< Σ
II(Q' Q) jz [|]l[(=rr]]]
< 2|
Q1
| ?
< 2$
|
and with probability 1 e-d we have Σn= ||,;|| < 5nd. Then,
-!Q-Q* - 12 ||Q' - 1²122 (Q", Q' - Q) < @1 Q11
vde.
13

---

Thus,
1
Σ I1Q --0:11 - } 10nde + -nvde
Σ i=1
IIQ Q'),;11² n n1Q -Q112
sup QEO(d)
sup QEA,
< max
Vn(A+ (ield//))l Q" 11. (
Cd
+ 10nde + nv
with probability 1 -2e 2ed -2e >x Thus, applying this to Q:
- -1Q-Q% Q*)aa, 1|² & ndd + d' max (Vno(A+ C +
Ca In(es) 10nde + nv
and taking 8/11,
Σ 112-0%) < 2nod + C +d(()))))))+++++)))))) Cf
leading to:
A+ Cd (n(1/5)) A + Cdd
(at < 40o2d 168d e
n
hence the result, taking À /n + d²
B.2 Proof of Lemma
Proof of Lemmn 3 Denote s(Q) Σ -0
Q yi The proof relies on noticing that for
all Q E (d), by definition ({) < g(Q") and using ||a + bl2
_llall ||b|| one gets
m
@2 Q) 2
g(Q) 2n
g(Q).
and thus 1. Ei= (Q Q)1l l|
< 4g( by applying the previous inequality TT. Usinn
lla + b1l2 & 2(1|a|12 (]b|1)) one gets:
x(Q2)=
xR(1) 2x - Q*
T2
20
< Σ ||0+()) - 2z1(3))
|| ||
n
20
26 ( x²) +
2 2
n
20
<
28d +
||
n
With probability 1
e e-d
5nd, and we are thus left with lower bounding Using results form the previous proof, with probability 2e-nod 2e -
Σ
||
Em Q Q)
we have:
1+o (2- l|= > n
100-0011 101 + ndd +
+ (n11/6)).
Thus, with probability 1-
eg eertio & dd + c' 18(A Cdl ( + 88d + 40o
leading to the desired result for A &f vn.
14

---

C Proof of Theorem 1
Proof of Theorem Define [(T, Q) = -. |[0(())) - Q vill". QTvilll can assume that ld.
Without loss of generality we
Step 1: using ML estimators.
By definition, the ML estimators (ft Q) defined in minimize L and
thus [(+, Q) f( Id, Q*), which can expressed as:
(a(()) QT - 24
n
71
Using ||a|2 < 2(1aa b1l2 + [|6112,, we obtain:
n (*() - Q'
46
n
|
T2
Then, standard chi-square concentration (see e.g. Laurent and Massart 2000)) entails that for all
I 0,
PP
nd
> ndt + 2f
< 2e
so that with probability 1 - 2e n Ei= ||: 2
< (d 2 + 2), and thus
Σ [R()) - -Q
50
(13)
for d (or n) large enough.
Step 2: existence of a set K. with prescribed properties. We will now show that the above inequality 13
forces ov( n² Id) to be large. To do so, let us assume that ov Id) < 5, for some > to be specified later: hence, there exist least nō indices i [n]] such that #(1) + i. Let define
|
30
I: i E [m]
[=(0)
Q' Q'
ozd
8
is clear that under the event B,, on which 13 holds, we have (n gives
[ o < 5no?d, d, which
n1 5/6)
Consequently, denoting
{ iE [m] (1) # *(1,, |+(0) QTQ'
l| < 5 o
30
J =
one has [ > nd (n [Z] on. We remark that for all i E J.
H E J (1))()) (,+()) + の) < 4.
Let us denote Q = Q Q' Iteratively ruling out at most 3 elements for each i E J, the above shows that event E,, build set K. = K(At, f Q) [n] such that
K nó/6.
(ii) for all K. #(1) a and (i, (E)) are disjoint pairs,
(i for all E K., || - Qui 1 & 2d.
15

---

Step 3: upper bounding the probaility of existence of such set K. We will now bound the probability that such a set K exists. First, let us fix i E [n], Q E Old), π E Sn such that x()) o i. We have
Iz(1) Quy (0, 21a). Assume 60o < 1 and ò 60o so that have 60 o d & d. For these 8
fixed Q, TT, we have
60 o 1 (INTO,WWII - (d (d- 11 1i)l > d/2) 4/16
[<>())>) Qe:l|
<
where we applied the one-sided chi-square concentration inequality
TP (P(K= (k-x22Vkr
exp(-x) when X x²)... This gives that for any given K.C. and (ii) above, using independence of the pairs (a(() liek and recalling that 5 > 60o one has
[n] satisfying conditions (i)
60 odd & -666666d/16 c e-nd//96
P ViEK ||x( - Quil| <
(14)
8
Denote by As the event As = (there exists
Sn, Q E O(d) and K. = K((T, Q) S [n] which satisfies (1), (ii) and (tit)
(15)
As previously explained, we want to bound the probability of the event As, for > 60a2. For the union bound on Q E (d)) we need to use an epsilon-net argument, which as follows. Let & > to
d²
be specified later. By Lemma 4. there exists Ng an s-net of (d) of cardinality at most which is also an e-net for the operator norm, see Remark In particular, if we are under event As and take x, Q2 KC verifying conditions in 15 there exists an element Qe of Od such that |1Q= @llop < E, which gives
30
Vi E KG, ||-<0) Q=aaI1 < | - Qr.1 + I1Q - 11)=x11 < o²d 1Q - Qloop |<v||
and applying chi-square concentration again gives that, under event Cn with probability > 22d and the above yields
1 e d+logn > 1 e 4/2 -d/2 since (d > 2 n) ) for all E [m). ||
30 o²d + v2d <
60 o²d.
Vi e K. ||==()) - Qe0:
choosing C2 02 for some appropriate 02 Hence, taking a union bound over E S,,, Qe (d) and subsets K S [n], and recalling (14). we can bound P (As B,) by
d²
civd E
P P(As| Bn, C.)
<
nl
2n -ōnd/96
(Bn,
< (1 + o()) exp(n logn + czd2 log d end (8/(02)+++0000000 + n csônd)
< (1 + o()) exp(_ccónd)
where we recall that > 60o22 and the last inequality holds if cad /0/(0²) & c7d2 & cgônd, and if czd2 log d & egônd for which 8 > codlog d/n suffices, and if n log n & ezônd, for which 5 2 c:0 log n/d suffices.
Step 4: conclusion. Now, wrapping things up, we obtain that for 8 max cod/nn /nd Ci log logn/d) n/d), we have for n large enough
P (ov(ft, x²) < 1
8) & P (Ba, C..) P (ov T3) < - Bn, C..) + TP (B, C..)
< P (As Ba, Cx) +P PB.) + IP (C,)
(1 + =[]]e -cgnd + 2 + dd2 o(1)
d/2
This gives the desired result
log n
ov( +) > 1 max 600g c1_ 02 dlog
which remains true when 60o² > 1.
The desired inequality for 2 (Q, Q*) follows from Lemma
3 (for 5 (d/nn) and Remark 1
U
again, see e.g. Laurent and Massart
2000
16

---

D Proof of Theorem 2
We here prove that a minimizer Q of the conic alignment loss satisfies the following guarantees.
Theorem 3 (Conic alignment minimizer). Let do E (0,1). Let = Let Vi...., Vq be i.i.d. uniform directions in Sá-1, and assume that u1 ,....., Up are independenty and uniformly distributed over (Ui,...,Puy) F- Let N be an e-net of (d)) (d) for the Frobenius norm of minimal cardinality. Then, there exist constants C1, C2, Cz. Cs. Os:Oz= 0 such that, if log(()) 2 godlog(1 ( C20d-112
then, with probability Ge-C.d 5 60. à p polylog(1/o,) and x log(1/6u)'
Czöj
d Q- l| c0.
Then, combinign this result with Lemma 2 setting as in Equation (1)). we obtain Theorem 2
D.1 Proof of Theorem 3
Proof of Theorem 3 Recall that K, 0 are for now any (small) positive number but can be specified later. do is the target error. We begin by giving a few notations, For the proof, we need to introduce the following probability
B x) == PX C(u, ||]|| > 1/k).
(16)
where X ~ (0, Ia) and a is any unit vector in R4. Note that 3(6, k) is independent of the choice of u by rotational invariance of Gaussian distribution. It easy check that IP (I, Cx (x,(u))) P (y E Cx(u, 8)) = 3(,, k) for any i,j and any unit vector
Step General strategy. Our goal is prove that w.h.p. have
F(Q) < inf (((Q), Q
((Q))QEN, E -Q ond].
(17)
for some & 0 be determined. This will entail that è 1- < 6od.
Step 2: An upper bound E [F(O)). Since N is e-net of O(d), there exists Q A such that
QQ: - 11 & Note that by optimality of Q one has F()) < F(Q2). We first upper bound the left hand side in 117 by upper bounding the expectation of F(Q:) using the following result.
Lemma 5. Let Q O(d), E Sd-1, We have:
[F())] 2n3(8, k)) (da
2Bo
+ p(Q' p(Q' + 2e BB2 + e ed))
B2
Gdd
for any B² > 0, where for some matrix M, p(M) is defined as its spectral radius.
Lemma 5 (rrovdd in next subsection) gives, for any B > 0:
F(Q) < F(Q2) = E [F())) + F(Q2) - [FF():)
< 2n,(5, m) (d'd
2Ba
+ p(Q' - Q)/5 + +2c 2 + +6-d) + F(Q2) - [F(())]
Voda
< m)) (d'd
2Bo
+ 2e- BB12 -B-B122 + =0)) + sup F(Q) E[
+ 8
(18)
6dd
QEN
where we used p(Q" - -²) <
Q
Q:
< in the above.
Step lower bound on R. [F()) for any Q lower bound the right hand side in 17 using the following Lemma.
17

---

Lemma 6. Let Q E O(d), E Sa-1. We have, conditionally on the directions u1..... Up
Σk=1 1 -1) -644320
[F(Q) UI....,, up] 20)3(6,R)
P
We recall that ((6, k) is defined in (T6) here above. In the sequel, we denote by Py (resp. By) the probability (resp. expectation) over the directions Wi,..-; Up. Lemma (proved next subsection) gives that inf ((Q).QEN, IQ Q"11 > 5od >
inf QEN 11Q Q" 1lp
B[F(Q)) sup QEN
20in3(0,
inf
BU
(19)
P
QEN 11Q Q" 1 2d0
sup ((Q) E (F(Q)]] QEN
(20)
Now, if we take dn 2 85 + 640, we have
inf QEN 11Q Q" 11 >ōud
Eu
(21)
inf QEN
Ey
Q1Q Q 113 >60d
inf QEN
Eu
110 10)-0-)ul1>>>> 10-0-12
11Q Q² fod
Lk=l
11 1Q-Q'11
p
inf QEN
Pu
Q')
2d
Q Q- >ood >ood
Note that if 2 ~ (0, la/d). by rotational invariance of the Gaussian, one can always write 2 = Nuj
where N = |||| and ύn
T are independent and uj is uniform on the sphere. This yields
Z
IQ 1
[I[Q - 21)
[Ne] Ry [I( Q*) 11 = [v - Q*),il1
We can lower bound the right hand side of the above using reverse Markov inequality, namely that (xX= > E /2) > E [X] /8 for any X such that < X < a.s. We apply this X
II(Q - )url" 1| and get that for all Q E N such that ||Q
Q* > dnd,
Pu (
IQ - Q'
IQ 1
50
11
2d
8d
8
and via Equation 21 Equation
19p becomes
Ci33(6
inf F(Q).QeN.I1 Q" 1 > dod
sup IF(Q)
E [F(Q)]] (22)
QEN
Step 4: Uniform concentration of F(Q) around its mean. The remaining step is to control the concentra-
tion of F(Q) uniformly N. This is given by the following.
Lemma 7 (Concentration of F). Let Q E O(d) be fixed. Recall that = p². that U1..... By are i.idd uniformly sampled on the sphere Sd-1 and that ui.... Up are i.i.d. uniformly sampled in {uI,..., ). We have for all X 0:
2 3 log(p) A
2AA2 +
())
IP [((Q)
(6,
< 40 > + 2e -2
/p
18

---

Hence, plugging À = 2 (V) > WP we have
(assuming W > 2) in Lemma 7
with probability at least
sup (F(Q) - B[F(Q)II QEN
(23)
< 8v (VVllg) 3log(p) + [o) + (log(p)2 + log() 9n3(o, k)
n n3(66, k)p
k)pp
$ lo max d² ( x)p 1/2
(24)
+ czdl log(1 max(log de log (
where we used log([N)) & c9d log(1/E) in the above.
Step Wrapping things up. Putting together the control on deviation in 23 the upper bound and the lower bound (22). one gets that with probability > 6/|W], , for any > 0:
inf F(Q). N: Q|Q - Q- 5nd
F(Q)
(25)
Cin3(6, k)ō0 2n,(6, k)
c'd
2Bo
B² + c-d +
+
4
66d
sup QEN
IF(Q) [[Q(]
n,3(5, R) Ciòn
x²)
cd
2Ba
+
+ 2 + te-d log(1/)) max(l))p)))(())))).))))))))))))) di log(1/=))) 1/2
12
6dd
czd log(1/E) max(log(p), de log(1 (1 p/112
(26)
If this lower bound is positive, we can conclude that @ 10-00 1'1 & dod, as desired.
1Q-Q'1
So far, the only constraints on our constants are
(A1) 80 88 + 646
While the noise parameter a is fixed in this proof, we have the freedom to impose some constraints on 6 (the granularity the e-nt)), 5 (the width of the cones), (the truncature parameter), p (the number of directions) and B in order to make the expression in (25 positive (and even >> 1). The remaining step is to show that this is possible this what we shall do now.
Recall that we are in a regime where we need to keepn in our minf that tends to +oo and d tends to too with n but with others: first, we would like to have an inequality of the form
log(n). We want to show that the positive term 25 can dominate the
8 ddd
2Bo Vol8
+ B²12 +e - -ca log(1/s) max(log(p), d log(L/s))p- 1/2 > cod0
4
(27)
which is going to be satisfied if:
(A2) C1 > ScB-
(A3) 6,d e7 d.
(A4) 6gd > cade,
(A5) & > cg(e / edd)
(A6) 6g > a log (1/s) max(log(p), log(1 (og(1/)))--1/ 1/2
where C7, C8, C9, C10 large enough constants. Now,
19

---

(A2) is easily verified by choosing Cs.
B only appears in (A3) and (A5). (A5) is satisfied if we take do > 2cge and B cn max(L, transforming (A3) into /max(1,log(1//0)))
C12Vdo; do;
appears in (A4) and can be taken as e Σ bud for this condition to be satisfied. Combined
ogd
with (A2), we can simply take & 67 v B/ (cæd) this condition to redundant;
p only appears in (A6) and can thus be taken as large as desired to have this inequality satisfied (very large p does not degrade any bound).
Consequently, the inequality in Equation 27 is satisfied for parameters that satisfy:
(A7) -ied 1/20,
(A8)
p2/2 2 C130
d log(d/o))
(A9) 60
(A10)
2 C15 do
max [1 log
thereby transforming the condition that the RHS in Equation 25 is positive into:
n3(6, k)) cled log(1 /e) max((og(p)) & log( (1/e)))pp log log( (ooggVdd))
The RHS of this inequality can be taken smaller than by imposing that p is large enough (recall that p can be taken large desired). The final condition thus reads as n,3(6, k) > 1, which is itself satisfied if
n 3 o' d'dlog(1/0) ---a/160-1
and IP (x1 E Cx(ua, 0)) > d'ddoog(2//8 while since k)) = Px E Cr(uo. o), |,|||| > 1/k)
P ([|=1] > 1/K) - dd/16 for
(A12) x² 2
d
assa:usmiiiiiillaaasssstipiooooo We are now going to use the low-dimensionality assumption d < log(n) since n 2 e dloo(1188)( e e-d/16) will be verified for
(A13) log(n) >> d'dlog(1/0) = cdd dllog(()/)))
Thus, under (A8-A13), Equation (25 is positive, and therefore have that :110 - 1112-Q''( & 60- m
D.2 Misceallenous lemmas on the path to proving Theorem 3
We introduce the (numerical) constants e, c' > 0 that verify, for all 8 e 10,1/4) that for æ sampled uniformly on gd-1 and any u S we have
exp d'd /8")) & &P P E C(u, < exp (- ed log(1
The following lemmas are used to prove Lemma and Lemma 5
'n our model, the probability P (x E C(u, 8')) can in fact be computed explicitly. For fixed d and the above probability given by (1/2)P (Xf > (1 - (X? ...xx))) where the (X.) are standard i.i.d.
Gaussian variables. It is standard that hence
x² І
is distributed according to the beta distribution /31/2, (d - 1)/2),
(1 C(u, 8')) = P (B(1/2, (001))
T(d/2)
112 (1-2)(d-33/ der
T(1/2)T(
(1-632
which is indeed of order dd when ó is small.
20

---

Proof of Lemma 5 We recall that for any i.j, P (a, E Cxx (), = Pv, E Cx(u, 6)) = ((6, k) for
any unit vector u. Taking the expectation and developing the indicators, we have
E [F()]
IP (Ea)()) E Cxx(Qus, 6)) - P P(u:= E Cy(us,))) 2TP (Far()) E Cx(Quus,))u E Cy(ux, 6)) P (Vi E CG((u,))) 6)]
2)(6,K)
(1 1- P (I E C(Qus, 1) > 1/K/us us E C(u,, 8), > v1+
p
kml im
= =2n3(d,k) k)
[ P [
> 1/K/r E C(u, > v1+02/x)).
where X ~ I.), Q'X + oZ with Z ~ NO, Ia) independent from X, and for any unit vector u. We thus need to bound the last term, which is done by noticing that the two events in the remaining probability become highly positively correlated when is close to Q". First, separate the norm component from the direction component in the event (X E C(Qu, 6), ||| > 1/k}:
P x E EC(QU. |X] > 1/m E C(u, 6), |V & V v1+02/K)
= (F(EEcQQu 0) 8) E(,, ||| > v1+ IP (IXXI > 1/MI| > v1+
> P x E C(Qu, ol E |Y| > V1- IP ( > 1/k).
Now, have yi E Cy(u, = (x)(() E Cx(QTu. u. 8 (e, u)) using Lemma 0.) 20 (Q"TT + p(Q²~ - -Q), so that:
12
where
P
(1)(1) C(Q.0) E Ilvll) v1+
P
(1) E EC(Q. u: E (((, E EC(Q,6+ Ibull > v1+02/k)
-ddlog (1 + 20 (2 (Q*) Tuyl
+ p(Q - -Q110) |10i1| V1+02/1
E
exp
[T)()))
[dddlog (1 + 2x B
+ +p(Q" (p(Q*=Q)100 -Q1/0) ) |||i|| > v1+00/ u) B¹
E
exp
8||5
x IP ((zx(((") u))l & B))
2n B
+ p(Q" - Q)/8) ) (1 - P (1(z) (Q+) u/}l > B))(1 P (11=m-(0)| > 1/k))
> exp
[ddlog (1 +
8
First, PP (1 > d (dd2///++
< e- for any
> 0, so that 1/x² > 3d,
P (11= > 1/k) E - +d
Then, (2,, (Q*)Tx))
u²)l ~ (N(0, 1)) since u us unitary, and thus TP (((),(Q1)TTT (Q*)) Tui]== > B) < 2c B212 &
2e -2 for B- = 2, leading to:
P (1 E C(Q,)) C((u,),, ||vill > v 1100//1)
> exp
-dddlog (1 +
2Bro
+ p(0*=())))))) -Q)()) ) (1
1B222222) - - td
8
> exp
(-ddlog(1 (1+
2No
+ p(Q* a1Q=-Q))00 2)/8) (1 2e -B2/2 c- cd))
V6d8
21

---

for x² = 1/(6d). Using log (1g + +) & and e- >>>>>> - x for x > 0,
IP (+)(1) c(Q.8) yr E C(u, 8), |mlll V + 02/xx)
-c'd(
2Bo
pQ QQ166 (1 22 -B²/2 Ed))
exp
Vod
cd( + p( Q)/6)
2Ba
2e -B212 E
V6d6
d'd
2Bo
+ p(Q" Q1/8
2e -2e-B² 13//2 end)
v6d0
leading to
- P (()()) EC(, EC(U, (), 1vell > v1 02/11)
< cd
2Bo
+ p( - Q)/8
+ +e 12 2 + -d
V6d8
and thus to the desired upper bound on (F))).
Proof of Lemma 7 We first begin by bounding all the terms that appear in the sum of F(Q). Define
A(u, Q) = |Cx 6)1 - (Cy(u, 0)),
so that F(Q) = Ek A(u: Q) Using Bernstein incquality (Vershynin 2018 Theorem 2.8.4],
and writing k) (1))(0) E Cx 6)) (so that E. [A(u, Q)] & n3(6, k)), we have:
t2/2
(IA(u, Q)1 > 2) 2exp
n1((8, k) 1/3
so that
n²((6, 12)
PP (A(u, Q)2 > nB(5, & 2exp
n3(6, + Vn3(6, k)t/3
3 3//B366 k)t
< 2 exx
+ 2ex
2
Now, we have:
3 3./n,loo k))t
P P(3E [a],
A(vi, nB(8,k)tt < 2exp
- log(o) + +eex
+ log(g))
2
= 4
for / = 4(3 (og()())) + A) + (log())++X) We now use MacDiarmid's inequality \Vershynin 9m3(6.x)
2018 Theorem 2.9.11, by seeing F(Q) F(Q) f(u1..... Up), conditionally the event Y [a], A(ve. Q)2 < [4(3logge + A) + Allog(a) + n13(5, k) B, to obtain
9n9(A,
pt?
P
> olve ( ((I(()) lo) A(ve, Q)² < B)
< 2 exp
2B
where = for.... Ug since the bounded difference inequality is then verified for constant 4B. Thus,
V2 4(3log(p) + A) + 4(log(g) (
n,3(0,k)
P ((0))EF(Q)V)
< - ^ 2c -23
vP
22

---

The problem here lies in the fact that E [F(Q)[V] = E [F()) may not always hold! Hopefully this in fact the case:
E B[F(Q)M = 1
E [[[Cx 6)1 - (Cy(cc 6)1) = me]
pq
E [[Cx(QQ,, 8)1 - [Cy(v,
for any fixed Sa-1
= [F(()))
concluding the proof.
Proof of Lemma
o Let 8 II(Q Q')uull (1) C((Qu,,)) 5) ys C(ux, 8). 1laall V1 + 0² ic, I1(Q Q²))ua > E
>
0 to be
determined
later and k We are going to show that is small.
E
[p] such
that
e.
P
Using Lemma
Yi E C(up. 5) implics that (z) E =CQ uk + 2 a
||ج=|||
Then, C(Qug, 5) n
C(Q" uk, 5 + 2 |=.1l
ø provided that IQuu Quusz] uu || > 4(0 +
-||=ا||
using Lemma 8
[
Thus, if QQu
Quuuul l? > E,
(1) C((QUR, 8) yi C(ux, (llux,)),ll 8) 2 vI+ I|( - Q*)uxl 2e)
0||=||1
4(8 + P
(+) ||
40 |=s|
<
> - 46
[|0x(())
We have P ||
> 4d)
< & and P (1==~<001 1|2 < < Edd1100, so that if E > 46 + 32a, we
have P
4r||
> E - 46
< TP ||=1| > 4d) + (1 &
16d -16d, leading to & e- + c
|
|[
P (x) (1) E EC(Qus, 5) ye E C( 8), |B:l|| > / IIQ Qu)aal > 8) & se 4/16 < 1-C1,
where C1 = 1/e + 1/e1/16 > 0 is numerical constant. This thus gives:
Eh-1 1 -hww--Qhuw1::0
[[(())U) > 2C1
p
Lemma 8 (Cone separation). For u, v E S0-1,
C(u,0) n C(u, 8) a Ø implies that ||u
vl|
< 85.
Proof. Assume C(u, 8) n C(u, 8) * Ø. Take w E C(u, 8) n C(v, 5): we can always assume that ||w|| = 1 by rescaling. Then, by triangle inequality, we have I|u mll & || wil + || w|l. Since
C(u, 8), ||u w||2 = 2(v, w) 2 2(1 8) 28, and the same is true for ||e w|I. This gives ||u v|| < 2025.
Lemma 9 (Probability that two cones are disjoint). Let Q. E O(d). & T Q2 - 2 and let u be a random variable uniformly distributed over 1d-1 Then,
PP (C(Q'u, n) 8) = 2) > 8.
Proof. Using the previous Lemma, P (C(Q'u, () 8) + x < PP (IQu Q'ul2 < 86) Let
Z be the random variable Z ||Qu Q'ulj2 We have that E | ||Q Q'Ip//d > 128 and
Z & 4 almost surely. Thus, using a "reverse Markov" inequality.
128 < E [2] = E [21zess] P (Z+ & 86) + E [[I2288 P (Z > 86)
< 88P Z < 86) + 4P (Z 86)
< 86 + - PXX < 88)),
that is IP (X & 86) < 6, which concludes the proof.
23

---

The following Lemma is easy and does require any proof.
Lemma 10. For any u, ō E (0, 1), we have E [ 8)1l nF (x) E(u, ||x 1/m) n3((,, k) so that (Cx(Qu, (Cy(u, 831 in the sum that de- fines F are all centered.
E El|Cy(u, 8)1l =
[Cx(u, 831 and Cy(u, 8)1 are (correlated) binomial random variables of parameters (n.3(ō, K)). Lemma 11. For any 84-1, i E [n], we have yi E Cy(u,) ||=]|| and (1) E Cx((Q)) T u. 8 + 6)) = Ys E Cy(u, 8). where 83 20 |=ll|
(xx((1) E Exx((Q") u, 5 8,),
where 6, = 20 |
M
Proof. Let us prove the first assertion and assume that yı E Cy(u, 8). We have y; - (1) to Cy(u, 6), which writes as:
(Q' (1))0 + 0 u) > (1 - -)) 0222
Thus,
(xx)(0) (Q*) u) > (1 "]|[0==x100 + 02 - o 022 (Q²)
R (1 0)[[0-=--10 + +02 - ||||||||
> (1 11 - a||
> (1
2x |||||
> (1 6 6-) Q")
which is the desired result. The second assertion is proved exactly in the same way.
Lemma 12. For any u E sd-1, i E [m]. Q E Odd), we have y: E Cy(u,)) = Zx((1) Cx(QT Sx(Qu,, ", + 5:(Q, u)), where 5:1Q,u. u) 2o (=x.1Q)T mill + p(Q² QQ. #atcol
Proof. Assume that y Cu, 8). As in the proof of the previous proposition, this reads as:
(x) (0) (Q*) T u) > (1 - 1-60)l00=x=1000 + oz - (Q") u),
and thus,
(x)) (4), Q TTu) > (1) (QT (Q-) - (1 0) xx xx + o2. - (25, (Q*)Ta) u) x (1) + 024 - 022 (()()))))))))))))))))
| Q') Q*) + +11 (1-6))lQ'
> | 1llp11l - Q*) + +(1 (1-5 (lc,.(2) T u/}l
|||| ||| ||||
(1 8 - &(Q. x 10||
This concludes the proof.
E Proof of Proposition
E.1
Very-fast sorting-based estimator and equivalence with one step of Frank- Wolfe
We have:
Vf(D) = 2 x -
for any bistochastic matrix D, leading to, for J = I1_:
n
VS()) = = 2Y TXX x +YTTrT)
For any permutation matrix P. we have since JT = J and JP J:
(JxTxXXX, x, P) = (XT 3XxXXXXJ X.JP) =XXXXXXX X x,J),
24

---

and similalry:
(yTyyTyJ,,) = (JY rY
Y,)).
Therefore,
arg min (JJ), = arg max (Y TYXX X, P). rES,
PES,
We have XX1 = (mi, R3) and (JXTX) [X)s = zz). Similarly, YYTYJ);; -n(..v))) and we have J = J. Thus,
(YTYJX x)xxxx))=-- = n Σ (0. (T,
leading to:
arg min, = arg max TES,
( yi) (z)
PES.
VE(M)
and the following sorting- sorting-based estimator, that can be computed very easily in ((nd (n)) computes.
# E arg max TES,
Σ 4) (vi, ()..
(28)
where 3 = I xy and y - Yi the mean vectors of each point cloud. The idea is that thanks to the scalar product, this estimator gets rid of the orthogonal trasformation. Its strength is that it be computed in O(n log(n)) iterations, since it consists in sorting two vectors. We have the following result for this estimator.
Proposition 2. Let 8 (0, 1) and Ifo & n satisfies with high probability:
12(1-26)
the estimator as defined Equation (8
ov n 1-8.
Proof. Without loss of generality, we can assume that nr = Id. Then, for all i,
(yt, 57) (Q'z
(z,, (t -(
so that:
1
(1) 2) (v,. 0)
(I(()) 1) (2,, .)-
(+(1) 2) [0² Q'z) o((
7
n
n
1
(x((1) x)
(2i, 2 x)
2n
+
(an())) 3) (02 + tz x) + oQ v,, x)]
By definition of न,, we have
1
Σn i= (x+(1)) Z) (B) 0) > + Σm (2,, t) (vi, Ø). that thus writes as:
1
2n (Ia(()
24, x),
(pa(1) F,, x) (2 8) + + Q' x) + a x,, m)]
n
1
sup (Zx(1) rr x) n2
0² (2 2) + 0 Q+ +
vE(n)
We will first bound this right hand side. First, for all j.j E [n]. I is independent from ã, so that conditionally on T we have (I, x) (0 2 i 2)) leading to:
IP (1 - ., || & 2 exp( -t/2),
25

---

and
P(vi. E (2) +|| < 22
zz.
so that with probability 1-2/n2,.uppp sup,, - < 2 2ogg) Similarly, with probability
1 4/n², sup, (2 Q*0)) < 2/log(1 (z) || and sup; (Q x4, E\| 2 2/log(m)]a]].
Then, we can write 2; = 2 + Σ where z/ is Gaussian (its covariance matrix the projection on the orthogonal of 2) and independent from 2. Thus, sup, (2, 2)1 < ||]| + sup, 2)) <
||a| 2 ||||||
with probability 1 1 2/nn..
Thus, with probability 1 8/n² and for 1
sup (0+(1) 3 Tb}l 71
o ( 2) (z + x; (
< 2 2log(m)o log |||||| + || + 4v log(n)|11]
Now, n||æ]| and n n|| are both xa random variables, so that
[max(|=]]=]] dl, |=| d|) 21 + vll
< 4t
Fort = 2(v2- - 1)d, this leads to, with probability 4e 1(
| 2 || E 3 d
Thus, with probability - -8/n² 4e
2(v2-1)d
1
sup EE
(0=(1)) 2,, T
0² (2 2) + t Q) + aQ" (Q",,;,]] 2)
71
< 20 2 (o) | 2 log(1) (2) - 3 d/n 4, 4 31)
for some numerical constant C, in > d, leading to
[I())) 5)² < Clog(n))o|1313.
2n
(a; xj < [|| PP 1)2 <t) < evt, for Now, if + j are fixed, for 1, P
some constant > 0.
We are now going upper bound the probability of the event A "there exists I C [ni] with [Z] 2 an and a permutation such that (i) for all i E I, (1) + i, (ii) fi, (1)) form disjoint pairs and (iii) for all i I, (I=()) I,, 2 < "| for some constants a, B E (0, to be fixed
later. Let and be fixed. Since (ii)= A i, have IP (5(Zz: Iz(1), x)2 > B|| 1²) 2e using (ii) all pairs are independent, leading to:
8/2 -/2 and
P (T, I satisfies (i)-(i))(iii)) & Vi ViEI,
2 [xx En(i), x)² > 3|
1
<c/B.
Thus, using a union bound over all possible I and æ., we have that:
P (AA) < n" -asnnaa/ttannn log(2)
tog log(2)
Now, using what we have proved above, denoting the event 1n4 (T=(( I,, x) < C' Cl we have IP (B) > 1- 8/n2 4e 2(v2-1jd Let C be the event {ov(ft & 1 - 1)
26

---

Under CnB, we have the existence o' C [n] such that for all indices i I', f * i and [Z] > ön/6. Now, since then शाश LiEz((##() Z4, x)² < C'oo(nn)o((31' we have that least half of these indices satisfy (T)(()) 0)2 < 12 ('
denote by I the set of these 5 and & = y/2 x C. Co)((n),, leading to indices. Hence, म, I satisfy properties (i)-(ū)-(iii)) with a T2 (taking these constants for A):
P(BNC) ( (AA)
<
ön log (12C8-1 l))(())) + n log(n) + 2n log(2)
exp
12
For this probability to be close to zero, we thus need that on log 10 log(n))) which can be written as:
> (1 + E) log(n).
12
log 11205-'lo((n))
12(1 + E) log(n)
log n 12044)
8
which is satisfied for 120+2e)
E.2 The "Ace" estimator
Proposition (Ace). Let 6n > O. Assume that 0 -0- < 2(1 50)d and logn & d & n.
Then, there exists constant such that the estimator कt defined in Equation satisfies with probability 1 2e-d//// 2n -;
C 6u
(Valogta/bb
log(n)
dllo(d/50)
+ log(n)
xf
max
n
n
In the >> d >> log(n) regime: as long we have non negligible error | 0²22² 2 e)d
(notice that for uniformly random Q, we have - Q- 2d), we recover " with 1 - o(1)
overlap: doing just a tiny bit better than random for Q is enough to recover n².
Proof of Proposition 3 In this proof we denote g(x) = EE (Fa()) (0(0)):0 y.). By definition, A E
arg max+es, g(T). Writing g(f) 2 g(T*) gives
(==()) (T))))))))
(1) a +
Σ (( Iz(1), Q 21) (29)
Without loss of generality, we assume a Id. The term the LHS hereabove, for fixed म,, Q has expectation ( -*) "T(TrQQQT)) We are going to compute uniform fluctuations. For some fixed Q E Odd, E S,,
Σ (umo = XTM,
for x= -x ...... 2n ) E Rud and M E &Bndxnn that writes M = PT Q where Q Budxxnd is block diagonal with blocks equal to Q, and P gadxnd is a block matrix, with blocks of size nd. Using Hanson-
that verify P(s) Ps Thus, ||
and ||M 1
Hanson-Wright Wright inequality,
IP Σ (c)(1), Qzi) - nov(T, Id) IT(Q) C(t + Vndtt
<
-t
2e
Since d > log(n), with probability 1 dd116 we have sup:elm] ||>ح|| We now work conditionally this event.
2vd using Chi concentration.
27

---

Letting Na a a
net net of O(d),
Vn S AQ E Na.
Σ (1x(s) Qx:) - nov(T, Id) Tr(Q)
> C(t + vndit
< 2c ttn (og(n)))) (og(1)))
Using the fact that Ei= (#x(()) Qua is nsuuselm] ||0|| 4nd
Lipschitt Q, we thus have:
Vt ,n VQ Odd), [( Qui) nov(T, Id) Tr(Q) 4ndō + C(I + vndi < 2e (otttooog))ntt log(1/8)
Setting
18 and 2n log(n) + off log(8/s), with probability 2n " we get that for all
T, Q,
nde
Σ ()) Qz)) - nov Id) Tr(Q)
<
+ (' + dl log(1/E) + v vnd(nlog(n) - dl log(1/E))))
4
We can thus write, since Tr(Q (('@(QQ)>)))))) > Ed:
dc log(1/s) (Cac))) Q'(mx=))))) < <TriQ" Q* )dov Id) + ed + C'log((n)
d2 (2log(1/E)
+ V vdllog(n)) +
n
n
and
(loog(()) + dc log(1/e) (Cr Q' TT( ed
+ d((lg(n) + da log (1/e)
n
Similarly than before, we prove that with probability 1 - 2n we have for all π E Sn, Q E O(d):
< Edn
Σ ((x00)--1(0)) TR()), iT 2.)
+ C' (nllon(()) + d log(1/s) + (nd(nlog()) + d2 (og(1/))))
4
Equation 29 thus implies that:
3ed
d Llo((1/E) 3C (log()) +
d2 log(1 /8) ))
Tr(Q (')dov(I, Id) > Tr(@QQn (d
+ d(log(n)
n
n
leading to:
35
30'
log(n) dloo(11/E)
log(n) dlog(1/E)
ov Id) >
4 TT<(QQQ" Q*)
Tr(
n
Setting
Ag d
concludes the proof.
E.3 Proof of Proposition| 1
Proof of Proposition ! For the first part of Proposition I we directly apply Proposition with
1/2 to obtain the result.
For the second part that holds for large dimensions, we apply Proposition for 1/2 and 1/8.
Using Lemma 3 first 'Ping' of leads Q satisfying the assumption of Proposition 3 for some 6y bounded away from zero, thus leading to the desired result after the last 'Pong' for ât
28

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The contributions and scope of the paper described shortly in the abstract. The introduction section discusses the contributions and the scope more in depth.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
The limitations of the paper are discussed, in particular the fact that our work is mainly theoretical, and we mainly study informational results.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sellsspeciiiationn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
29

---

Answer: [Yes]
Justification: The paper provides the set assumptions in every Theorem and Proposition,
that self-contained
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Section 3.3 lists all the needed information to replicate all the experiments in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
30

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
supplementary materials for notebook.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ ccippi.cc guwdes/ddeeeee CooeeSumeeieeeeeeeeeee ssi onyylicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: All the details of training procedure and hyperparameters are listed in Sec- tion 3
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: the experiments are merely illustrative and due to the n² scaling of the LAP, we performed some averagings over 10 runs for each point. But this can be improved easily in a second version.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
31

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification: In preparing the submission, the authors did track sufficient information the computer resources. However, the resources needed to run experiments are minimal, as all can be
single CPU. The total compute resources needed are not significant.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http:///aara..c.ppppo/acaacccaaa
Answer: [Yes]
Justification: The paper conforms with the NeurIPS Code of Ethics and does not pose any potential harm.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper is foundational research paper without any direct societal impact.
Guidelines:
32

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymentt of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
The paper uses Python with some open-source Python libraries for experiments. There are no other particular existing assets used.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
33

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
If assets are released, the license, copyright information, and terms use in the datasets.paperssiii paperswi thcode. www.coo//aaaaa datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
There are no released assets in the paper.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodll as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
34

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
35


Reviews:
[{"review_id": "nERN2xHZCw", "reviewer": "Reviewer_6nbD", "summary": "This paper studies the theoretical limits of the Procruste-Wasserstein problem which consists in finding an optimal assigment of cloud of points in Euclidean space up to a global rotation. The paper focuses on the model of a cloud of point perturbed by a global rotation and some gaussian noise. The authors establish theoretical results on the recovery of the optimal rotation and the optimal assigment in two cases of interest: high-dimension/low number of samples and low dimensions/high number of samples. They also propose a Frank-Wolfe type of algorithm with an initial step based on convex relaxation: this algorithm is shown to perform better than other state of the art algorithm.", "questions": "Why is the conical alignment loss not used in practical experiments? Is it because it gives poor practical performances?", "limitations": "not applicable.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is extremely well-written, it is easy to read. In my opinion, the questions addressed in the paper are of interest to the community interested in geometric alignment. The improvement upon Grave's algorithm seems interesting as well.\nThe estimator in the low-dimensional case introduced the idea of slicing along one-dimensional subspace and it is remarkable that this idea which was used in other contexts, works well in this low-dimensional problem.", "weaknesses": "The theoretical results are interesting for a relatively narrow audience of NeurIPS.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's positive feedback and the valuable comments.\nWe answer the question raised below.\n\n*Why is the conical alignment loss not used in practical experiments? Is it because it gives poor practical performances?*\nThe conical alignment loss is useful for informational results only, and is not used in practical experiments because its computational complexity is very high. The reason is that one has to optimize over an $\\varepsilon-$net of asymptotic size $(\\sqrt{d}/\\varepsilon)^{d^2}$, and each evalutation on this $\\varepsilon-$net has complexity $O(pn)$ where $p \\geq \\mathrm{polylog}(1/\\sigma, d)$. This yields a total complexity which is superexponential in $d$.  \nIn other words, the statistical performances of the conical alignment loss are strong, while its computation efficiency is not. We do however believe that the conical alignment loss could be a path towards more efficient algorithms for this problem, that could seek at approximately minimizing this loss.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BMU1T5cFMm", "reviewer": "Reviewer_ERNU", "summary": "This submission is concerned with the problem of aligning planted graphs. To this end, both a permutation $\\pi$ and an orthogonal matrix $Q$ must be estimated from observations of $X$ and $Y$. To evaluate the performance of this approach, it is proposed to measure to measure the error induced by $Q$ in terms of the squared Frobenius norm to the true underlying matrix $Q^{\\star}$ (denoted $\\ell^2(Q,Q^{\\star})$) whereas the error induced by $\\pi$ is given by $c^2(\\pi,\\pi^{\\star})=\\frac 1 n\\sum_{i=1}^n||x_{\\pi(i)}-x_{\\pi^{\\star}(i)}||^2$. \n\nThe first contribution of this work is to provide information-theoretic results for this problem. Namely, the simple maximum likelihood estimators for $\\hat \\pi$ (which can be efficiently computed) and $\\hat Q$ (which has a closed form solution) recover $\\pi^{\\star}$ and $Q^{\\star}$ almost exactly in the limit of vanishing noise in the high-dimensional regime ($d\\geq 2\\log n$). In the low-dimensional regime $d\\ll \\log n$, it is shown that if the noise is of the order $o(d^{-1/2})$, then estimators $\\hat Q,\\hat \\pi$ can be formulated for which $c^2(\nhat \\pi,\\pi^{\\star})=o(d)$ and $\\ell^2(\\hat Q,Q^{\\star})=o(d)$. It is shown, moreover that the good performance of one of the two estimators can be transferred to the estimator in a straightforward (and computationally tractable) manner.\n\nNext, as the PW problem is equivalent to the quadratic assignment problem (QAP) which is known to be NP-hard in general, a convex relaxation of the QAP is considered which consists of maximizing the objective over all bistochastic matrices. The proposed algorithm for approximating the QAP consists of first solving the relaxed problem via the Frank-Wolfe algorithm then using this solution to hot start an alternating minimization procedure for the permutation matrix and the orthogonal matrix. Guarantees for one step of this algorithm are then provided. The paper concludes with some numerical experiments which shows that the proposed Ping-Pong algorithm generally outperforms direct resolution of the relaxed QAP and the method of Grave et al.", "questions": "The authors are kindly requested to answer to the above point. \n\nI noted the following typos:\n1. line 139: is its probability -> if its probability.\n2. line 279: envelop -> envelope.", "limitations": "The assumptions are clearly stated in each relevant result.", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is well-written and places itself well within the existing literature on this problem. \n\nTo my understanding, the high dimensional results are first of their kind whereas the low dimensional results improve on previously known results. The proposed algorithm is also seen to perform best out of the other considered.", "weaknesses": "The analysis of the proposed ping-pong algorithm is quite limited. The one-step result provided in Proposition 1 is already an interesting step in the analysis, but  it would be interesting to see a more refined analysis. Given the fact that the QAP problem is NP hard it is clear that we cannot expect particularly strong results in general (e.g. convergence to global minimizer), but it may be possible to discern some properties of the matrices to which the algorithm converges or to provide a bound on the number of iterations required in certain cases.\nAt the very least it would be useful to recall the per iteration complexity.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thorough reading and reviewing, positive assessment, and very positive feedback which will help improve the quality of the paper in its second version.\nWe answer the questions raised in the review below.\n\n*The analysis of the proposed ping-pong algorithm is quite limited. The one-step result provided in Proposition 1 is already an interesting step in the analysis, but it would be interesting to see a more refined analysis.*\nOur analysis of the Ping-pong algorithm is indeed limited to a 1-step version. As acknowledged in the paper, we did not manage to analyze the Ping-pong algorithm in a more detailed way for two reasons: *(i)* the initialization is a hard problem to study (as we argue at the beginning of Section 3.2, there are no guarantees for the relaxed QAP) and *(ii)* the alternative minimization steps eluded our analysis so far due to the non-convexity of the minimization steps.\nHowever, it is to be noted that, unlike previous results for relaxed QAP (such as Valdivia and Tyagi, 2023), Proposition 1 offers recovery guarantees for non-null noise (even though the noise is required to be small enough).\nDeepening our understanding of the Ping-pong algorithm is a challenging work in progress.\n\n\n*Given the fact that the QAP problem is NP-hard it is clear that we cannot expect particularly strong results in general (e.g. convergence to global minimizer), but it may be possible to discern some properties of the matrices to which the algorithm converges or to provide a bound on the number of iterations required in certain cases. At the very least it would be useful to recall the per iteration complexity.*\nWe will recall the per iteration complexity of the Ping-pong algorithm in a revised version.\nFor the initialization, each of the $T$ steps of Frank-Wolfe algorithm is a LAP that has complexity $O(n^3)$ (which can be reduced to $O(n)$ via entropic regularization at the cost of approximations). \nThe SVD in the ‘Ping' step has complexity $O(d^3)$ while the LAP in the ‘Pong' step has complexity $O(n^3)$ (again, entropic regularization can reduce this to $O(n)$).\nThe overall complexity of the algorithm is thus $O(Tn^3+ K(n^3+d^3))$ (or $O((K+T)n+ Kd^3)$ if we use entropic regularization).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "61dpmiV6dS", "reviewer": "Reviewer_JfWm", "summary": "This paper studies the Procrustes-Wasserstein problem that aims to match two high-dimensional point clouds where one is a noisy version of the other up to an orthogonal transformation. The authors establish information-theoretic results in the high ($d \\gg \\log n$) and low ($d \\ll \\log n$) dimensional regimes. Further, the authors also propose a \"Ping-Pong algorithm\" that alternatively estimates the orthogonal transformation and the matching. Sufficient conditions for the method to recover the planted signal after one step is provided. The theoretical finds are also supported by numerical experiments.", "questions": "1. How do the statistical guarantees for the proposed algorithm compare to the information-theoretic results? It would be nice if the authors could remark on this.\n2. Are there any negative information-theoretic results, i.e., lower bounds on the costs, for the Procrustes-Wasserstein Problem of the planted model?\n3. Can there possibly be computational-statistical gaps for the problem?", "limitations": "The authors addressed most limitations of the work. Some additional ones are highlighted in Weaknesses and Questions sections.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper defines a planted model for the Procrustes-Wasserstein problem that extends the work of Kunisky and Niles-Weed [2022] and Wang et al. [2022].\n2. Focusing on the $L_2$ transport cost between the point clouds, in contrast to previous works that mostly consider the overlap, the authors established information-theoretic limits in the low-dimensional regime ($d \\ll \\log n$), which substantially differ from those of Wang et al. [2022], and in the high-dimensional regime ($d \\gg \\log n$),\nwhich was not explored before.\n3. A \"Ping-Pong Algorithm\", first initialized by a Franke-Wolfe convex relaxation, then alternatively estimating the orthogonal transformation and the relabeling, is proposed. Statistical guarantees for *one single step* of the algorithm is analyzed.", "weaknesses": "1. Due to technical challenges, only guarantees for one step of the proposed algorithm is analyzed.\n2. The recovery guarantees are only provided in the overlap metric rather than the $c^2$ loss which is claimed to behave very differently when $d$ is small.\n3. The dependency on the noise parameter $\\sigma$ in the statistical rates seems to be different from that of the ML estimators. The tightness of the results in terms of $\\sigma$ is unknown.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's feedback and questions, that will help improve the clarity of the paper. We answer the questions raised below.\n\n*Due to technical challenges, only guarantees for one step of the proposed algorithm is analyzed.*\nThis is indeed true, our analysis of the Ping-pong algorithm is indeed limited to a 1-step version. As acknowledged in the paper, we did not manage to analyze the Ping-pong algorithm in a more detailed way for two reasons: *(i)* the initialization is a hard problem to study (as we argue in the beginning of Section 3.2, there are no guarantees for the relaxed QAP) and *(ii)* the alternative minimization steps eluded our analysis so far due to the non-convexity of the minimization steps.\nHowever, it is to be noted that unlike previous results for relaxed QAP (such as for instance Valdivia and Tyagi, 2023), Proposition 1 offers recovery guarantees for non-null noise (even though the noise is required to be small enough).\nDeepening our understanding of the Ping-pong algorithm is a challenging work in progress.\n\n*The recovery guarantees [of the Ping-pong algorithm] are only provided in the overlap metric rather than the loss which is claimed to behave very differently when $d$ is small.*\nFor small dimensions, the overlap metric and the $c^2$ transport cost indeed behave very diffently: a guarantee in terms of $c^2$ cost cannot be translated into a guarantee in terms of overlap.\nHowever, even for small dimensions, guarantees in terms of overlap metric (as the one of Proposition 1) can be translated in terms of transport cost, since we always have $c^2(\\pi,\\pi') \\leq  \\max_{i,j} \\Vert x_i-x_j\\Vert_2^2 \\times (1-\\text{overlap}(\\pi,\\pi'))$.\nFor large dimensions, we have $\\max_{i,j}\\Vert x_i-x_j\\Vert_2^2 =O(d)$ whp, while for small dimensions we have $\\max_{i,j}\\Vert x_i-x_j \\Vert_2^2 =O(d\\log(n))$ whp.\nWe will add such a discussion in a revised version.\n\n*The dependency on the noise parameter in the statistical rates seems to be different from that of the ML estimators.*\nThis assertion is true: The ML estimator as in Wang et al., 2022 has guarantees that are expressed in terms of overlap metric, while our guarantees are expressed in terms of transport cost $c^2$, which leads to signal recovery even for noise $\\sigma$ that does not tend to 0.\n\n*Are there any negative information-theoretic results, i.e., lower bounds on the costs, for the Procrustes-Wasserstein Problem of the planted model?* and *the tightness of the results in terms of $\\sigma$ is unknown.*\nThe tightness of our results is still an open question we are working on. Hence, we thank you for your inquiry; this is indeed an interesting point. We think that the IT results in the paper are sharp, at least in small dimensions, and not far from being sharp in high dimensions. We believe that whatever the value of $d$, when $\\sigma \\not \\to 0$, one should be able to show that the optimization problem has many solutions, and that some of them are far from the ground truth, in the $c^2$ as well as the $\\ell^2$ sense.\n\n*How do the statistical guarantees for the proposed algorithm compare to the information-theoretic results? It would be nice if the authors could remark on this.*\nThe statistical guarantees for the Ping-pong algorithm (Section 3) are weaker than the information-theoretic results of Section 2.\nWhile in Section 2 we are able to recover some signal (in the $\\ell^2$ and $c^2$ sense) as long as $\\sigma \\not \\to 0$, Proposition 1 requires $\\sigma\\to 0$ at a polynomial rate in $n$ to recover any signal for the Ping-pong algorithm.\nHowever, experiments suggest that the Ping-pong algorithm still recovers some signal even for $\\sigma=\\Omega(1)$, suggesting that our analysis is suboptimal, leaving this question open for future works.\n\n*Can there possibly be computational-statistical gaps for the problem?*\nThis is a very interesting question, that we did not investigate yet.\nComparing known computational results (Proposition 1 in our paper; the results from Gong and Li, 2024), there is still a gap between our informational results, and the cited computational results.\nHowever, we believe that this gap is mostly due to suboptimality of the analyses.\nThere might be computational-statistical gaps, but investigating these would require using specific methods, for instance the low-degree methods (Hopkins, 2018, *Statistical Inference and the Sum of Squares Method*) that has proven to be efficient for planted recovery problems like the one we are interested in", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tlIabPcd7b", "reviewer": "Reviewer_dVzJ", "summary": "The authors consider the alignment problem between a point cloud generated from a Gaussian distribution and its noisy version under orthogonal transformation, formulated as the Procrustes-Wasserstein problem. The authors derive information-theoretic results for both high and low dimensional regime (i.e., bounds on the maximum likelihood estimators to the optimal one). Additionally, the authors also propose an alternating algorithm, namely Ping-Pong algorithm, which is a variant of the algorithm in Grave et al. (2019). Empirically, the authors show advantages of the proposed algorithm over other baselines.", "questions": "It is interesting to generalize the problem considered in Kunisky and Niles-Weed (2022) into the considered Procrustes-Wasserstein problem. I have some following concerns:\n+ The title seems misleading. Could the authors comment on the relation between the considered problems in line 29-39 with random graphs in the title?\n+ Could the authors elaborate why it is interesting to consider Procrustes-Wasserstein problem between a point cloud generated from Gaussian distribution and its noisy version under orthogonal transformation? \n+ For the high dimensional regime, why do we need lower-bound on \\pi, but upper bound on Q? How’s about the upper-bound on \\pi, and lower-bound on Q – do they have some roles in the considered problem setting?\n+ For the Algorithm 1, why is it possible to fix T, and K? Does the algorithm converge? Is it possible to have some reasonable stopping conditions?\n+ Could the authors clarify why the algorithm 1 is superior to the algorithm in Grave et al. (2019)? It is better to deepen the analysis and illustrate with rigorous empirical evidence? E.g., with large number of data points (e.g., in Figure 1, it shows for n <= 200).\n+ In line 104-108, the authors emphasize the difference with other related works. Additionally, as in Figure 1, the authors also consider the case where d=2 and d=5, it is not clear why these approaches are not considered as baselines (as claimed in line 102-103). Could the authors clarify it?\n+ When Q*= I, could the authors compare the presented results with those in Kunisky and Niles-Weed (2022)?\n+ The Procrustes-Wasserstein problem is a non-convex problem. It is better to consider its initialization problem as well. It is not clear about the importance of the one-step analysis for Ping-pong algorithm in the context of nonconvex optimization? Could the authors clarify it?\n\n---------\nThe rebuttal has addressed some of my concerns, I increase the score to 5.", "limitations": "It seems there is no discussion on the limitation.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "+ The authors derive the upper bound (or lower bound) of the maximum likelihood estimator to the optimal one for the Procrustes-Wasserstein (PW) problem in both high and low dimensional regime.\n+ The authors propose a variant alternating algorithm, namely Ping-Pong for the PW problem, and illustrate its advantages over other baselines.", "weaknesses": "+ The title seems misleading. It is not clear about its relation with random graphs.\n+ The motivation of the considered problem seems weak. It is better to elaborate the problem. (e.g., why it is interesting to consider point clouds generated from a Gaussian distribution and its noisy version under orthogonal transformation)\n+ It is not clear about the advantage of the proposed Ping-Pong algorithm over the alternating algorithm considered in Grave et al. (2019). It is better to deepen analysis and empirical evidences.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the time spent reviewing and all the remarks and questions that will help clarify our paper. We make sure to address the concerns raised below.\n\n\n*The title seems misleading. Could the authors comment on the relation between the considered problems in line 29-39 with random graphs in the title?* There is a strong connection between the PW (Procrustes-Wasserstein) problem and GGA (geometric graph alignment), as we argue in our paper.  \nIn GGA, we observe two complete random graphs and try to recover an underlying node correspondence $P^*$. The randomness in this model comes from edge weights which are induced by a Gaussian model: The weights are scalar products between unobserved gaussian random vectors. Note that applying an orthogonal map $Q^*$ to all the vectors leaves the scalar products invariant.  \nIn PW on the other hand, we directly observe the vectors and want to recover both $P^*$ and $Q^*$.  As described in section 'Geometric graph alignment' of the introduction, the two problems (GGA and PW) are equivalent. This is formalized in Lemma 1, for which a proof is given in Appendix A.  \nTo make it clearer, we propose to highlight Lemma 1 more in a revised version since it clarifies the title.\n\n\n*Could the authors elaborate why it is interesting to consider Procrustes-Wasserstein problem between a point cloud generated from Gaussian distribution and its noisy version under orthogonal transformation?*\nThis is a fundamental question which can be answered as follows. Many learning problems on real-world data can be phrased as  optimization problems, which are often difficult in their worst case formulation, meaning the case where *any* instance of the problem is considered. A common approach to understanding a problem's hardness and deriving algorithmic guarantees is to consider the *planted version* of these problems, that is when data has more structure. This structure stems from a signal (here: an underlying alignement $P^*$ and an orthogonal transformation $Q^*$), and noise (here: Gaussian noise). The benefits of this approach is that we have a precise understanding of why the problem is easy or difficult based on the signal-to-noise ratio $\\sigma$. For a broad introduction on planted problems, we refer to the survey on community detection by C. Moore, https://arxiv.org/pdf/1702.00467, page 5.\n\n\n*For the high dimensional regime, why do we need lower-bound on $\\pi$, but upper bound on $Q$? How’s about the upper-bound on $\\pi$, and lower-bound on $Q$ – do they have some roles in the considered problem setting?*\nAn upper bound on $\\ell^2$ (for $Q$) and a lower bound on the overlap of $\\pi$  point in the same direction: To show that recovery is possible, a larger overlap is better and a lower $\\ell^2$-loss is better as well.\n\n\n*For the Algorithm 1, why is it possible to fix T, and K? Does the algorithm converge? Is it possible to have some reasonable stopping conditions?*\nIt is possible to fix $K,T$ arbitrarily, depending on the computation power available.\nEmpirically, the algorithm converges after $O(1)$ iterations.\nThe smaller the signal-to-noise ratio, the larger the number of required iteration.  \nWe show in Proposition 1 that if $\\sigma$ is small enough, $K,T=1$ is already sufficient.\n\n\n*Could the authors clarify why the algorithm 1 is superior to the algorithm in Grave et al. (2019)? It is better to deepen the analysis and illustrate with rigorous empirical evidence? E.g., with large number of data points (e.g., in Figure 1, it shows for n <= 200)* \nIntuitively, our algorithm is better than that of Grave et al. (2019) since it is more ‘greedy' at each iteration.\nEmpirically, Figure 1 shows that this is indeed the case for the whole considered range of parameters. The superiority is even stronger for small signal-to-noise ratios and large dimensions.\nWe propose, as suggested by the reviewer, to extend our empirical analysis to larger number of data points ($n$ larger) and larger dimensions.\n\n\n*In line 104-108, the authors emphasize the difference with other related works. Additionally, as in Figure 1, the authors also consider the case where d=2 and d=5, it is not clear why these approaches are not considered as baselines (as claimed in line 102-103). Could the authors clarify it?* \nIn figure 1, we consider $d=2$ and $d=10$. These are no baselines; they are respectively meant to capture both the small dimension  ($d << \\log(n)$) and large dimension ($d>> \\log(n)$) settings, as our paper shows that there is a dfference between these two regimes.\n\n\n*When Qstar = I, could the authors compare the presented results with those in Kunisky and Niles-Weed (2022)?*\nThis is the content Table 1: in particular, we show that for small dimensions, since we consider the $c^2$ transport cost, we are able to recover some signal even for $\\sigma=\\Omega(1)$, whereas Kunisky and Niles-Weed (2022) require much smaller signal-to-noise ratio ($\\sigma<<n^{-1/d}$).\nWe will make this comparison clearer in the paper.\n\n    \n*The Procrustes-Wasserstein problem is a non-convex problem. It is better to consider its initialization problem as well. It is not clear about the importance of the one-step analysis for Ping-pong algorithm in the context of nonconvex optimization? Could the authors clarify it?* \nDue to lack of space, we refer to our detailed answer in the rebuttal to Reviewer ERNU (first part). \n\n*It seems there is no discussion on the limitation.*\nWe propose to discuss the limitations of our work more clearly in a new separate paragraph, such as the problems left open, negative lower bounds and sharpness of our results, a deepened analysis of our algorithm and its initialization, the existence of computational-to-statistical gaps, and planted problems as tractable proxies for more complex problems.\n\nWe hope that our rebuttal answers the reviewer's main questions. We would greatly appreciate an adjusted review score if the concerns are lifted, and remain available for questions.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies theoretical results for finding an alignment between two sets of points, where the distribution of the first set of points is the orthogonal transformation of the other set of points, up to some noise. Although there are some concerns about the motivation of the problem to a general audience, all reviewers agree that the theoretical results are novel and meaningful. Reviewer concerns were also addressed over multiple discussions during the rebuttal phase.

I would encourage the authors to address reviewer concerns and make improvements to the overall presentation, to strengthen the potential impact of the work.
Decision: Accept (poster)