Aligning Embeddings and Geometric Random Graphs: Informational Results and Computational Approaches for the Procrustes-Wasserstein Problem

Authors: mathieu  even
jakob  maier
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 17:32:33

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).

Main paper: 
 introduction: 
 Finding an alignment between high dimensional vectors or 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 as 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 R d . Some approaches are based e.g. on optimal transport and Gromov-Wasserstein distance Alvarez-Melis and Jaakkola [2018] or adversarial learning [Zhang et 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 -to higher dimensions Hoshen and Wolf [2018] . Another recent contribution is that of Grave et al. [2019] , where a 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.To formalize this problem, we consider a Gaussian model in which both datasets X, Y ∈ R d×n (or two point clouds of n datapoints in R d ) are sampled as follows. First, X = (x 1 , . . . , x n ) is a collection of i.i.d. N (0, I d ) Gaussian vectors, and Y = (y 1 , . . . , y n ) is a noisy version of X = (x 1 , . . . , x n ), up to an orthogonal transformation Q ⋆ and a relabeling π ⋆ : [n] → [n] of the data points, that is:∀i ∈ [n] , y i = Q ⋆ x π ⋆ (i) + σz i , (1) or, in matrix form: Y = Q ⋆ X(P ⋆ ) ⊤ + σZ , where Z = (z 1 , . . . , z n ) ∈ R d×n is also made of i.i.d. N (0, I d ) Gaussian vectors, P ⋆ is the permutation matrix associated with some permutation π ⋆ , 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 a lack of theoretical results to guarantee their performance or to exhibit regimes where they fail. Model (1) described here above appears to be the simplest one to obtain such guarantees. We are interested in pinning down the fundamental limits of the Procrustes-Wasserstein problem, hence providing an ideal baseline for any computational method to be compared to, before delving into computational aspects. Our contributions are as follows:(i) 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, we establish 1 : (i.a) information-theoretic results in the high-dimensional d ≫ log n regime which was not explored before for this problem;(i.b) new information-theoretic results in the low-dimensional regime (d ≪ log n) for our metric of performance (the L 2 transport cost), which substantially differ from those obtained in Wang et al. [2022] for the overlap.(ii) We study computational aspects and propose the 'Ping-Pong algorithm', alternatively estimating 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 stateof-the-art method of Grave et al. [2019] .One can check that under the above model (1), the maximum likelihood (ML) estimators of (P ⋆ , Q ⋆ ) given (X, Y ) is given by:EQUATIONwhich is strictly equivalent 2 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 P ⋆ is known then (2) boils down to the following orthogonal Procrustes problem:EQUATIONwhich has a simple closed form solution given by Q = U V ⊤ where U SV ⊤ is the singular value decomposition (SVD) of Y (XP ⋆ ) ⊤ (see Schönemann [1966] ). Conversely, when Q ⋆ is known, (2) amounts to the following linear assignment problem (LAP in the sequel):EQUATION1 this very dichotomy (d ≫ log n versus d ≪ log n) is fundamental in high dimensional statistics and not a mere artifact of our rationale; see Remark 1.2 their matrices X and Y are the transposed versions of ours.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 a permutation π ⋆ on [n] and n i.i.d. pairs of correlated Gaussian vectors (X π ⋆ (i) , Y i ) in R d with noise parameter σ, they observe matrices A = X ⊤ X and B = Y ⊤ Y (i.e all inner products ⟨X i , X j ⟩ and ⟨Y i , Y j ⟩) and are interested in recovering the hidden vertex correspondence π ⋆ . The maximum likelihood estimator in this setting writes arg minEQUATIONwhich 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 a 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(log n), where geometry plays the most important role (see Remark 1). They prove that exact (resp. almost exact) recovery of π ⋆ is information-theoretically possible as soon as σ = o(n -2/d ) (resp. σ = o(n -1/d )). They conduct numerical experiments which suggest good performance of the celebrated Umeyama algorithm [Umeyama, 1988] , which is confirmed by a follow-up work by Gong 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π ⋆ if σ = o(d -3 n -2/d ) (resp. σ = o(d -3 n -1/d )), hence coinciding with the information thresholds up to a poly(d) factor. However, their algorithm is of time complexity at least Ω(2 d n 3 ), which is not polynomial in d. This is 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 [2024] , because (i) we are also interested in the high dimensional case d ≫ log n, and (ii) we work with a different performance metric which provides less stringent conditions for the recovery to be feasible, see Section 1.2. A summary of previous informational results together with ours (see also Section 2) is given in Table 1 .On the orthogonal transformation Q ⋆ . Generalizing the standard linear assignment problem, our model described above in (1) introduces an additional orthogonal transformation Q ⋆ across the datasets. This orthogonal transformation can be motivated in the context of aligning embeddings in a high-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. [2019] . 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 Q t of the orthogonal transformation, we sample mini-batches X t , Y t of same size b and find the optimal matching P t between Y t Q ⊤ t and X t , via solving a linear assignment problem of size b. This matching P t 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 be 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 t = (x t,j ) j∈ [b] and Y t = (y t,j ) j∈ [b] are chosen independently, if b ≪ √ n it is likely that for any matching π t the pairs (x t,j , y t,πt(j) ) always correspond to disjoint pairs, and thus aligning Y t Q ⊤ t and X t does not reveal any useful information about the true P ⋆ -this is even more striking when the data is non-isotropic.Notations. We denote by X ∼ N (µ, Σ) with µ ∈ R d and Σ ∈ R d×d the fact that X follows a Gaussian distribution in R d of mean µ and covariance matrix Σ. If µ = 0 and Σ = I d , variable X is called standard Gaussian. We denote by O(d) the orthogonal group in dimension d, and by S n the group of permutations on [n] . Throughout, ∥ • ∥ and ⟨•⟩ are is the standard euclidean norm and scalar product on R d , and ∥ • ∥ F and ∥ • ∥ op are respectively the Frobenius matrix norm and the operator matrix norm. The spectral radius of a matrix A is denoted ρ(A). In all the proofs, quantities c i where i is an integer are unspecified constants which are universal, that is independent from the parameters. Finally, all considered asymptotics are when n → ∞. Note that d also depends on n. An event is said to hold with high probability (w.h.p.) if its probability tends to 1 when n goes to ∞.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 π ⋆ 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 π ⋆ via the overlap:EQUATIONdefined for any two permutations π, π ′ . 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 2 transport cost between the point clouds. The natural intuition is that a mismatch is less costy if it corresponds to embeddings which are in fact close in the underlying space. We definec 2 (π, π ′ ) = 1 n n i=1 x π(i) -x π ′ (i) 2 ,for any two permutations π, π ′ . Note that this cost can also be written in matrix form as c 2 (P, P ′ ) = (P -P ′ )X ⊤ 2 F . From this form it is clear that, as stated before, c 2 (P, P ′ ) is nothing but the euclidean transport cost for aligning XP ⊤ onto X(P ′ ) ⊤ . Note that these two measures, ov and c 2 , are also well-defined 3 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:ℓ 2 (Q, Q ′ ) = ∥Q -Q ′ ∥ 2 F ,3 for the overlap, one could extend its definition using that ov(P, P ′ ) = ⟨P, P ′ ⟩. defined for any two orthogonal matrices Q, Q ′ .Comparison between metrics. For a Haar-distributed matrix Q on O(d), we have that E ℓ 2 (Q, Q ⋆ ) = 2d, while for π sampled uniformly from the set of all permutations, we have E c 2 (π, π ⋆ ) = 2d(1 -1/n) and E [ov(π, π ⋆ )] = 1/n. Hence, some estimators π, Q of π ⋆ , Q ⋆ will perform well in our metrics if they can achieve ℓ 2 (Q, Q ⋆ ) ⩽ εd, and c 2 (π, π ⋆ ) ⩽ εd for some small (possibly vanishing) ε > 0.Depending on dimension d, similarity measures given by c 2 and the overlap can behave differently or coincide. In the case where d is small, and thus plays a very important role, ov and c 2 have very different behaviors, and lead to very different results. In particular, there is a wide regime in which inferring π ⋆ for the overlap sense is impossible, but reachable in the transport cost sense, see Section 2.For any fixed permutation π, we have thatE c 2 (π, π ⋆ ) = 2d(1 -ov(π, π ⋆ )), where the mean is taken with respect to the randomness of X. We also have the basic deterministic inequalityc 2 (π, π ⋆ ) ⩽ (1 -ov(π, π ⋆ )) × sup (i,j)∈[n] 2 ∥x i -x j ∥ 2 .Thus, as long assup (i,j)∈[n] 2 ∥x i -x j ∥ 2 = O(d), an estimator π with good overlap (1 - ov(π, π ⋆ ) ⩽ ε) also has a good c 2 cost (c 2 (π, π ⋆ ) = O(εd)). However, this required control sup (i,j)∈[n] 2 ∥x i -x j ∥ 2 = O(d) 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 c 2 . 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 ε > 0, denoting X = {x i , i ∈ [n]}, we have that P (B ∩ X = ∅) → 1 if d ≫ log(n), while if d ≪ log(n) then for all M > 0, P (|B ∩ X | ⩾ 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 no such points w.h.p.2. For d ≫ log(n), matrix X/ √ d satisfies the restricted isometry property [Candès, 2008] .3. For d ≫ log(n), the overlap and the transport cost metrics are equivalent: there exist numerical constants α, β > 0 such that w.h.p., for all permutation matrices π, π ′ ,αc 2 (π, π ′ ) ⩽ 2d(1 -ov(π, π ′ )) ⩽ βc 2 (π, π ′ ).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 3 some computational results, introducing the Ping-Pong algorithm, and presenting our numerical experiments.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 are 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 in 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 as long as it is clear that these goals are not attained by the paper. 
informational results: 
 The substantial theoretic part of the paper stands in the informational results obtained for the Procrustes-Wasserstein problem which we describe hereafter.In the high-dimensional case when log n ≪ d (and d log d ≪ n), our results -Theorem 1 belowimply that if σ → 0 then the ML estimators defined in (2) satisfy w.h.p.ov(π ⋆ , π) = 1 -o(1), c 2 ( P , P ⋆ ) = o(d), and ℓ 2 ( Q, Q ⋆ ) = o(d),that is one can infer π ⋆ and Q ⋆ almost exactly, for all introduced metrics, as soon as σ → 0.Note that this is the first result in 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 is recovering π ⋆ 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 c 2 and the overlap sense, since these metrics are equivalent in large dimensions (see Remark 1). Our result is in fact more specific and only requires d ⩾ 2 log n. We prove the following Theorem: Theorem 1. Assume that d ⩾ 2 log n. There exists universal constants c 1 , c 2 , c 3 > 0 so that for n large enough, with probability 1 -o(1), the ML estimators defined in (2) satisfyEQUATIONandEQUATION)The proof of Theorem 1 is detailed in Appendix C and builds upon controlling the probability of existence of a certain subset of indices K( Q, π, Q ⋆ ) of vectors with prescribed properties in order to show that π ⋆ can be recovered. We apply standard concentration inequalities to control the previous probability. The d ⩾ 2 log(n) assumption is crucial here since it allows the union bound over S n to work.In the low-dimensional case when d ≪ log n, Theorem 2 below implies that if σ = o(d -1/2 ) then there exist estimators π, Q that satisfy w.h.p.c 2 ( P , P ⋆ ) = o(d), and ℓ 2 ( Q, Q ⋆ ) = o(d) ,that is, one can approximate π ⋆ (in the c 2 sense only) and Q ⋆ as soon as σ = o(d -1/2 ). This is of course to be put in contrast with the previous results on geometric graph alignment in this lowdimensional regime: for almost exact recovery in Wang et al. [2022] in the overlap sense, we need σ = o(n -1/d ), which is far more restrictive than σ = o(d -1/2 ) as soon as d log(d) < log n, that is nearly in the whole low dimensional regime when d ≪ log n. In particular, since the rates of Wang et al. [2022] are sharp when d is of constant order, in order to approximate π ⋆ in the overlap sense it is necessary to have σ to decreasing polynomially (at rate 1/n 1/d ) to 0, whereas approximating π ⋆ in the transport cost sense requires only σ = o(1).There is no contradiction here, since we recall that the c 2 metric and the overlap are not equivalent in small dimensions: let us give a few more insights on this. This scaling n -1/d comes from the fact that in small dimensions, points of the dataset are close to each other, and the order of magnitude between some x i and its closest point in the dataset scales exactly as n -1/d : if the noise is smaller than this quantity, one should be able to recover the planted permutation. However, when it comes to considering the c 2 metric, matching i with j such that ∥x i -x j ∥ 2 ≪ d is sufficient, thus suggesting that recovering a permutation with small c 2 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).Our main theorem for low dimensions is as follows.Theorem 2. Let δ 0 ∈ (0, 1). There exist estimators π, Q of π ⋆ , Q ⋆ such that if for some numerical constantsC 1 , C 2 > 0 we have σ ⩽ C 1 δ 2 0 d -1/2 and log(n) ⩾ C 2 d log(1/δ 0 ), then: c 2 (π, π ⋆ ) 2d ⩽ δ 0 and ℓ 2 ( Q, Q ⋆ ) 2d ⩽ δ 0 .A refined version of Theorem 2, namely Theorem 3, 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 1 required the union bound over S n 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 is 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 π, Q. When d = 1, Q ⋆ = ±1 and a simple strategy to recover Q ⋆ is to count the number N + (X ), N -(X ) (resp. N + (Y), N -(Y)) of positive and negative x i (resp. positive and negative y j ): if N + (X ) and N + (Y) are close, then we output Q = +1, whereas if N + (X ) and N -(Y) 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 is exponentially big in d. Our strategy is thus as follows. We compute the number of points that lie in a given cone C(u, δ) of given angle δ and direction u. Then, we estimate Q ⋆ by the orthogonal transformation Q which makes the number of y j in C(u, δ) closest to the number of x j in C( Qu, δ), for any direction u. Note that this approach heavily relies on the small dimension assumption d ≪ log n: in this case, for any constant δ, all theses cones contain w.h.p. a large number of points (tending to ∞ with n), which does not hold anymore when d ≫ log n.For δ > 0 and u ∈ S d-1 , let C(u, δ) := v ∈ R d | ⟨u, v⟩ ⩾ (1 -δ)∥v∥ be the cone of angle δ centered around u. Let X := {x i , i ∈ [n]}, Y := {y i , i ∈ [n]}.We now introduce the following sets, for some κ > 0:C X (u, δ) := X ∩ C(u, δ) ∩ B(0, 1/κ) C and C Y (u, δ) := Y ∩ C(u, δ) ∩ B(0, 1 + σ 2 /κ) C ,where B(0, r) C contains all vectors in R d of norm larger than or equal to r. The role of κ > 0 is to prevent side effects: indeed, since the cones are centered at the origin, points that are 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 u 1 , . . . , u p ∈ S d-1 to be set later, we define the following conical alignment loss:EQUATIONThe estimator Q in Theorem 2 is then defined as a minimizer of the conical alignment loss over a finite setN ⊆ O(d): Q ∈ arg min Q∈N F (Q) ,where N will further be some ε-net of O(d), while π is then obtained by a LAP as in (10).2.3 From P ⋆ to Q ⋆ and vice versaIn 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.1 and B.2.Lemma 2EQUATION)that can be computed in polynomial time (complexity O(n 3 )) as the solution of a LAP, satisfies:c 2 (π, π ⋆ ) d ⩽ C 1 δ + C 2 σ 2 + C 3 max d ln(1/δ) n , ln(1/δ) n .Lemma 3(From P to Q). Let δ ∈ (0, 1/2).Assume that there exists π that is σ({x 1 , . . . , x n , y 1 , . . . , y n })-measurable such that c 2 (π, π ⋆ ) ⩽ δd. Let Q be the solution to the following optimization problem: There exist constantsEQUATION)that can be computed in closed form with an SVD of XY ⊤ , satisfies:ℓ 2 ortho ( Q, Q ⋆ ) d ⩽ C 1 δ + C 2 σ 2 + C 3 max d ln(1/δ) n , ln(1/δ) n .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 no 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 (e.g., independence assumptions, noiseless settings, model well-specification, 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 a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness. • 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 acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
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 ( 9) are of course not poly-time in general. In this section, we are interested in computational aspects of the problem.Estimating P ⋆ can be made via solving the QAP ( 5), that can be convexified into the relaxed quadratic assignment problem (relaxed QAP):Prelaxed ∈ arg minEQUATIONwhere D n is the polytope of bistochastic matrices, which is the convex envelope of the set of permutation matrices. Note that unlike in ( 5), this argmin is not necessarily equal toarg max P ∈Dn ⟨P ⊤ X ⊤ XP, Y T Y ′ ⟩ since D n contains non-orthogonal matrices.The estimate Prelaxed gives a first estimate to then perform alternate minimizations in Q through an SVD -see ( 11) -and P through a LAP -see ( 10). Combining an initialization with convex relaxation, computed via Frank-Wolfe algorithm [Jaggi, 2013] and the alternate minimizations in P and Q yields the Ping-Pong algorithm.Algorithm 1: PING-PONG ALGORITHM Grave et al. [2019] 's algorithm, as explained in the introduction. The difference lies in the steps in Lines 6-7 of Algorithm 1: while Grave et al. [2019] perform projected gradient steps, our approach is more greedy and directly minimizes in each variable. Both approaches are experimentally compared in Section 3.3.Input: Number of Frank-Wolfe steps T , number of alternate-minimization steps K, P0 = 11 ⊤ n for k = 0 to T -1 do Compute S k = arg min P ∈Sn ⟨P, ∇f ( Pk )⟩ (LAP), where f (P ) = X ⊤ XP -P Y ⊤ Y 2 F Pk+1 = (1 -γ k ) Pk + γ k S k for γ k = 1 2+k P 0 = PT and Q 0 = I d for k = 0 to K -1 do Q k+1 = U k V ⊤ k for Y P k X ⊤ = U k D k V k the SVD of Y P k X ⊤ (Ping) P k+1 ∈ arg max P ∈Sn ⟨P, Y ⊤ Q k+1 X⟩ (LAP) (Pong) Output: P K , Q K Algorithm 1 is structurally similar toProviding statistical rates for the outputs of Algorithm 1 is a challenging problem for two reasons. First, relaxed QAP is not a well-understood problem: the only existing guarantees in the literature are for correlated Gaussian Wigner models in the noiseless case (i.e., σ = 0 in our model) [Valdivia and Tyagi, 2023] , while for correlated Erdös-Rényi graphs, the relaxation is known to behave badly in general [Lyzinski et al., 2016] . Secondly, studying the iterates in lines 6 and 7 of the algorithm is challenging, since these are projections on non-convex sets. While Lemmas 2 and 3 show that if P k (resp. Q k ) has small c 2 loss, then Q k+1 has small ℓ 2 loss (resp. P k+1 has small c 2 loss), showing that there is a contraction at each iteration 'à la Picard's fix-point Theorem' remains out of reach for this paper. We thus resort to proving that one single step of Algorithm 1 (K = T = 1) can recover the planted signal, provided that the noise σ is small enough.Proposition 1. There exists C > 0 such that for any δ ∈ (0, 1), if σ ⩽ n -13 δ , then the permutation π associated to the outputs π, Q of Algorithm 1 for K = T = 1 satisfies, with probability 1 -1/n: In the high-dimensional setting (d ≫ log(n)), there exist some constants c 1 , c 2 such that if σ ⩽ n -c1 , then π satisfies w.h.p.ov(π ⋆ , π) ⩾ 1 -δ .ov(π ⋆ , π) ⩾ 1 -c 2 max d log(d) n + log(n) d , d log(d) n + log(n) d .Thus, for σ polynomially small in n and exponentially small in 1/δ, one step of Alg. 1 recovers π ⋆ in the overlap sense with error δ. In large dimensions, this is improved, since σ is no longer required to be exponentially small as the target error decreases to zero. Proof of Proposition 3 is given in Appendix E.We compare in Figure 1 our Alg. 1 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 Frank-Wolfe algorithm with T = 1000 steps, enough for convergence. This estimator is then taken as initialization for Alg. 1 and Grave et al.[2019]'s algorithm, that are 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 et al. [2019] (smaller batches lead to even worse performances).We establish new informational results for the Procrustes-Wassertein problem, both in the high (d ≫ log n) and low (d ≪ log n) 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] .We start by proving Lemma 1 which gives the equivalence between PW and geometric graph alignement.A.1 Proof of Lemma 1Proof of Lemma 1. We have by Lemma 3 that as soon as we are able to estimate π ⋆ with a 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 and B = Y ⊤ Y of geometric graph alignement from an instance (X, Y ) of PW from model (1), 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 A = X ⊤ X, B = Y ⊤ Y of two correlated random geometric graphs under the Gaussian model from [Wang et al., 2022, Gong and Li, 2024] wherey i = x π ⋆ (i)+ σz i , we can recover π ⋆ via solving PW. Indeed, A is of rank at most d, so we can buildX ′ = (x ′ 1 | . . . |x ′ n ) ∈ R d×n such that A = X ′⊤ X ′ . Similarly, we can build Y ′ = (y ′ 1 | . . . |y ′ n ) ∈ R d×n such that B = Y ′⊤ Y ′ . We have X ⊤ X = X ′⊤ X ′ , hence ⟨x i , x j ⟩ = ⟨x ′ i , x ′ j ⟩, thus there exists Q 1 ∈ O(d) such that for all i ∈ [n], x ′ i = Q 1 x i . Similarly, there exists Q 2 ∈ O(d) such that for all i, y ′ i = Q 2 y i .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 obtainedX ′ , Y ′ which satisfy y ′ i = Q ⋆ x ′ π ⋆ (i) + σz ′ i for all i, where Q ⋆ = Q 2 Q ⊤ 1 , and x ′ i = Q 1 x i , z ′ i = Q 2 z i are i.i.d. standardGaussian vectors. This is 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.Throughout the proofs, we will need to give high probability bounds on quantities for all orthogonal matrices. This is done by covering O(d) by a finite number of open balls centered at points of O(d). This is done by considering ε-nets.Definition 1 (ε-nets of O(d)). Let ε > 0. A subset N ε ⊆ O(d) is a ε-net of O(d) for the Frobenius norm if for all O ∈ O(d) there exists O ε ∈ N ε such that ∥O -O ε ∥ F ⩽ ε. Remark 2. Note that since ∥ • ∥ F ⩽ ∥ • ∥ op by Cauchy-Schwarz any ε-net of O(d)for the Frobenius norm is also an ε-net of O(d) for the operator norm.We will need ε-nets of O(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 (ε-nets of O(d) of minimal size, see e.g. Rogers [1963] ). There exists a universal constant C > 0 such that for all ε > 0, there exists an ε-netN ε of O(d) such that |N ε | ⩽ C √ d ε d 2 . B Remaning proofs of Section 2 B.1 Proof of Lemma 2 Proof of Lemma 2. Denote g(π) := 1 n n i=1 x π(i) -Q⊤ y i 2. The proof relies on noticing that for all π ∈ S n , by definition g(π) ⩽ g(π) and using ∥a + b∥ 2 ⩾ 1 2 ∥a∥ 2 -∥b∥ 2 , one getsg(π) ⩾ 1 2 c 2 (π, π) -g(π),and thus c 2 (π, π) ⩽ 4g(π). We apply the previous inequality to π = π ⋆ and using ∥a + b∥ 2 ⩽ 2(∥a∥ 2 + ∥b∥ 2 ), one gets,g(π ⋆ ) ⩽ 2 n n i=1 (I d -Q⊤ Q ⋆ )x i 2 + 2σ 2 n n i=1 Q⊤ z i 2 = 2 n n i=1 ( Q -Q ⋆ )x i 2 + 2σ 2 n n i=1 ∥z i ∥ 2 ,where we used the fact that the matrices Q, Q ⋆ are orthogonal. Using concentration of Chi squared random variables, we haveP n i=1 ∥z i ∥ 2 ⩾ nd + 2 √ ndt + 2t ⩽ e -t ,leading to P n i=1 ∥z i ∥ 2 ⩾ 5nd ⩽ e -ndby plugging in t = nd. We are now left withEQUATIONF ; however, Q depends on the x i so we need a uniform upper bound. Using Hanson-Wright inequality, for any Q ∈ R d×d ,P n i=1 ∥(Q -Q ⋆ )x i ∥ 2 ⩾ n∥Q -Q ⋆ ∥ 2 F + c max nt∥Q -Q ⋆ ∥ 2 F ∥Q -Q ⋆ ∥ 2 op , t∥Q -Q ⋆ ∥ 2 op ⩽ 2e -t ,which reads as, for Q orthogonal (leading to ∥Q -Q ⋆ ∥ op ⩽ 2):P n i=1 ∥(Q -Q ⋆ )x i ∥ 2 ⩾ n∥Q -Q ⋆ ∥ 2 F + c ′ max nt∥Q -Q ⋆ ∥ 2 F , t ⩽ 2e -t .For ε ∈ (0, 1/2), let N ε be an ε-net of O(d) of minimal cardinality; by Lemma 4 we have log(|N ε |) ⩽ Cd 2 ln(d/ε). Using a union bound:P sup Q∈Nε n i=1 ∥(Q -Q ⋆ )x i ∥ 2 -n∥Q -Q ⋆ ∥ 2 F ⩾ c ′ max nt∥Q -Q ⋆ ∥ 2 F , t ⩽ 2e -t+Cd 2 ln(d/ε) .Taking t = λ + Cd 2 ln(d/ε), we have with probabiliy 1 -2e -λ that:sup Q∈Nε n i=1 ∥(Q -Q ⋆ )x i ∥ 2 -n∥Q -Q ⋆ ∥ 2 F ⩽ c ′ max n(λ + Cd 2 ln(d/ε))∥Q -Q ⋆ ∥ 2 F , λ + Cd 2 ln(d/ε) Now, if Q, Q ′ ∈ O(d) satisfy ∥Q -Q ′ ∥ F ⩽ ε,we have using the orthogonality property of these matrices:n i=1 ∥(Q -Q ⋆ )x i ∥ 2 - n i=1 ∥(Q ′ -Q ⋆ )x i ∥ 2 = 2 n i=1 ⟨(Q ′ -Q)x i , Q ⋆ x i ⟩ ⩽ 2 n i=1 ∥(Q ′ -Q)x i ∥∥Q ⋆ x i ∥ ⩽ 2∥Q ′ -Q∥ op n i=1 ∥x i ∥ 2 ⩽ 2ε n i=1 ∥x i ∥ 2 ,and with probability 1 -e -nd we haven i=1 ∥x i ∥ 2 ⩽ 5nd. Then, ∥Q -Q ⋆ ∥ 2 F -∥Q ′ -Q ⋆ ∥ 2 F = ⟨Q ⋆ , Q ′ -Q⟩ ⩽ ∥Q ⋆ ∥ F ∥Q ′ -Q∥ F ⩽ √ dε .Thus,sup Q∈O(d) n i=1 ∥(Q -Q ⋆ )x i ∥ 2 -n∥Q -Q ⋆ ∥ 2 F ⩽ sup Q∈Nε n i=1 ∥(Q -Q ⋆ )x i ∥ 2 -n∥Q -Q ⋆ ∥ 2 F + 10ndε + n √ dε ⩽ c ′ max n(λ + Cd 2 ln(d/ε))∥Q -Q ⋆ ∥ 2 F , λ + Cd 2 ln(d/ε) + 10ndε + n √ dε ,with probability 1 -2e -nd -2e -λ . Thus, applying this to Q:n i=1 ( Q -Q ⋆ )x i 2 ⩽ nδd + c ′ max nδ(λ + Cd 2 ln(11/δ)), λ + Cd 2 ln(1ε) + 10ndε + n √ dε ,and taking ε = δ/11,n i=1 ( Q -Q ⋆ )x i 2 ⩽ 2nδd + c ′ nδ(λ + Cd 2 ln(11/δ)) + c ′ (λ + Cd 2 ln(11/δ)) ,leading to:c 2 (π, π ⋆ ) ⩽ 40σ 2 d + 16δd + c ′ δ λ + Cd 2 ln(11/δ) n + c ′ λ + Cd 2 ln(11/δ) n , hence the result, taking λ = √ n + d 2 . B.2 Proof of Lemma 3 Proof of Lemma 3. Denote g(Q) := 1 n n i=1 x π(i) -Q ⊤ y i 2 .The proof relies on noticing that forall Q ∈ O(d), by definition g( Q) ⩽ g(Q ⋆ ) and using ∥a + b∥ 2 ⩾ 1 2 ∥a∥ 2 -∥b∥ 2 , one gets g( Q) ⩾ 1 2n n i=1 (Q -Q)y i 2 -g(Q),and thus1 n n i=1 (Q -Q)y i 2 ⩽ 4g(Q ⋆ )by applying the previous inequality to π = π ⋆ . Using ∥a + b∥ 2 ⩽ 2(∥a∥ 2 + ∥b∥ 2 ), one gets:g(Q ⋆ ) = 1 n n i=1 x π(i) -x π ⋆ (i) -Q ⋆⊤ z i 2 ⩽ 2 n n i=1 x π(i) -x π ⋆ (i) 2 + 2σ 2 n n i=1 ∥z i ∥ 2 = 2c 2 (π, π ⋆ ) + 2σ 2 n n i=1 ∥z i ∥ 2 ⩽ 2δd + 2σ 2 n n i=1 ∥z i ∥ 2 .With probability 1 -e -nd , n i=1 ∥z i ∥ 2 ⩽ 5nd, and we are thus left with lower bounding1 n n i=1 (Q -Q)y i 2 .Using results form the previous proof, with probability 1 -2e -nd -2e -λ we have:1 1 + σ 2 n i=1 ( Q -Q ⋆ )y i 2 ⩾ n Q -Q ⋆ 2 F + nδd + c ′ nδ(λ + Cd 2 ln(11/δ)) + c ′ (λ + Cd 2 ln(11/δ)) .Thus, with probability 1-ℓ 2 ortho ( Q, Q ⋆ ) ⩽ δd + c ′ n -1 δ(λ + Cd 2 ln(11/δ)) + c ′ n -1 (λ + Cd 2 ln(11/δ)) + 8δd + 40σ 2 d , leading to the desired result for λ = d 2 + √ n. C Proof of Theorem 1 Proof of Theorem 1. Define L(π, Q) := 1 n n i=1 x π(i) -Q ⊤ y i 2 .Without loss of generality we can assume that π * = Id.Step 1: using ML estimators. By definition, the ML estimators (π, Q) defined in (2) minimize L and thus L(π, Q) ⩽ L(π ⋆ = Id, Q ⋆ ), which can be expressed as:1 n n i=1 x π(i) -Q⊤ Q ⋆ x i -σ Q⊤ z i 2 ⩽ σ 2 n n i=1 ∥z i ∥ 2 .Using ∥a∥ 2 ⩽ 2(∥a -b∥ 2 + ∥b∥ 2 ), we obtain:1 n n i=1 x π(i) -Q⊤ Q ⋆ x i 2 ⩽ 4σ 2 n n i=1 ∥z i ∥ 2 .Then, standard chi-square concentration (see e.g. Laurent and Massart [2000] ) entails that for all t > 0,P n i=1 ∥z i ∥ 2 -nd ⩾ 2 √ ndt + 2t ⩽ 2e -t , so that with probability 1 -2e -n , 4σ 2 n n i=1 ∥z i ∥ 2 ⩽ 4σ 2 (d + 2 √ d + 2), and thusEQUATIONfor 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(π, π ⋆ = Id) to be large. To do so, let us assume that ov(π, Id) < 1 -δ, for some δ > 0 to be specified later: hence, there exist at least nδ indices i ∈ [n] such that π(i) ̸ = i. Let us defineI := i ∈ [n] : x π(i) -Q⊤ Q ⋆ x i 2 ⩽ 30 δ σ 2 d .It is clear that under the event B n on which (13) holds, we have(n -|I|) × 30 δ σ 2 d ⩽ 5nσ 2 d, which gives |I| ⩾ n(1 -δ/6) .Consequently, denotingJ := i ∈ [n] : π ⋆ (i) ̸ = π(i), x π(i) -Q⊤ Q ⋆ x i 2 ⩽ 30 δ σ 2 d , one has |J | ⩾ nδ -(n -|I|) ⩾ 5 6 δn. We remark that for all i ∈ J , |{j ∈ J : {i, π(i)} ∩ {j, π(j)} ̸ = ∅}| ⩽ 4 .Let us denote Q := Q⊤ Q ⋆ . Iteratively ruling out at most 3 elements for each i ∈ J , the above shows that on event E n one can build a setEQUATION) for all i ∈ K, π(i) ̸ = i, and (i, π(i)) i∈K are disjoint pairs,(iii) for all i ∈ K, x π(i) -Qx i 2 ⩽ 30 δ σ 2 d.Step 3: upper bounding the probaility of existence of such a set K. We will now bound the probability that such a set K exists. First, let us fix i ∈[n], Q ∈ O(d), π ∈ S n such that π(i) ̸ = i. We have x π(i) -Qx i ∼ N (0, 2I d ).Assume 60σ 2 < 1 and δ ⩾ 60σ 2 so that we have 60 δ σ 2 d ⩽ d. For these fixed Q, π, we haveP x π(i) -Qx i 2 ⩽ 60 δ σ 2 d ⩽ P ∥N (0, I d )∥ 2 ⩽ d/2 = P d -∥N (0, I d )∥ 2 ⩾ d/2 ⩽ e -d/16 ,where we applied the one-sided chi-square concentration inequality4 P k -X ⩾ 2 √ kx ⩽ exp(-x) when X ∼ χ 2 (k).This gives that for any given K ⊂ [n] satisfying conditions (i) and (ii) above, using independence of the pairs (x i , x π(i) ) i∈K and recalling that δ ⩾ 60σ 2 , one hasEQUATION)Denote by A δ the eventA δ := {there exists π ∈ S n , Q ∈ O(d) and K = K(π, Q) ⊆ [n]which satisfies (i), (ii) and (iii)} .(15) As previously explained, we want to bound the probability of the event A δ , for δ ⩾ 60σ 2 . For the union bound on Q ∈ O(d), we need to use an epsilon-net argument, which is as follows. Let ε > 0 to be specified later. By Lemma 4, there existsN ε an ε-net of O(d) of cardinality at most c1 √ d ε d 2, which is also an ε-net for the operator norm, see Remark 2. In particular, if we are under event A δ and take π, Q, K verifying conditions in (15), there exists an elementQ ε of O ε (d) such that ∥Q ε -Q∥ op ⩽ ε, which gives ∀i ∈ K, x π(i) -Q ε x i ⩽ x π(i) -Qx i + ∥(Q -Q ε )x i ∥ ⩽ 30 δ σ 2 d + ∥Q ε -Q∥ op ∥x i ∥,and applying chi-square concentration again gives that, under an event C n with probability ⩾ 1 -e -d+log n ⩾ 1 -e -d/2 since (d ⩾ 2 log n) for all i ∈ [n], ∥x i ∥ ⩽ √ 2d and the above yields ∀i ∈ K, x π(i) -Q ε x i ⩽ 30 δ σ 2 d + ε √ 2d ⩽ 60 δ σ 2 d, choosing ε = c 2 σ 2 /δP (A δ | B n , C n ) ⩽ 1 P (B n , C n ) × n! × c 1 √ d ε d 2 × 2 n × e -δnd/96 ⩽ (1 + o(1)) exp(n log n + c 3 d 2 log d + c 4 d 2 δ/(σ 2 ) + n log 2 -c 5 δnd) ⩽ (1 + o(1)) exp(-c 6 δnd)where we recall that δ ⩾ 60σ 2 , and the last inequality holds if c 4 d 2 δ/(σ 2 ) ⩽ c 7 d 2 ⩽ c 8 δnd, and if c 3 d 2 log d ⩽ c 8 δnd for which δ ⩾ c 9 d log d/n suffices, and if n log n ⩽ c 8 δnd, for which δ ⩾ c 1 0 log n/d suffices.Step 4: conclusion. Now, wrapping things up, we obtain that for δ ⩾ max(60σ 2 , c 9 d/n, c 1 0 log n/d), we have for n large enoughP (ov(π, π ⋆ ) < 1 -δ) ⩽ P (B n , C n ) P (ov(π, π ⋆ ) < 1 -δ | B n , C n ) + P Bn ∪ Cn ⩽ P (A δ | B n , C n ) + P Bn + P Cn ⩽ (1 + o(1))e -c6δnd + 2e -n + e -d/2 = o(1) .This gives the desired resultov(π ⋆ , π) ⩾ 1 -max 60σ 2 , c 1 d n , c 2 log n d log d ,which remains true when 60σ 2 ⩾ 1.The desired inequality for ℓ 2 ( Q, Q ⋆ ) follows from Lemma 3 (for δ = Θ(d/n)) and Remark 1.We here prove that a minimizer Q of the conic alignment loss satisfies the following guarantees.Theorem 3 (Conic alignment minimizer). Let δ 0 ∈ (0, 1). Let q = p 3 . Let v 1 , . . . , v q be i.i.d. uniform directions in S d-1 , and assume that u 1 , . . . , u p are independently and uniformly distributed over {v 1 , . . . , v q }. Let N be an ε-net of O(d) for the Frobenius norm of minimal cardinality. Then, there exist constantsC 1 , C 2 , C 3 , C 4 , C 5 > 0 such that, if log(n) ⩾ C 1 d log(1/δ 0 ), ε = C 2 σd -1/2 , δ = δ 0 , κ = 2 d , p ⩾ polylog(1/σ, d) and σ ⩽ C3δ 2 0 log(1/δ0) , then, with probability 1 -6e -C4d 2 , 1 d Q -Q ⋆ 2 F ⩽ δ 0 .Then, combinign this result with Lemma 2, setting π as in Equation ( 10), we obtain Theorem 2.Proof of Theorem 3. Recall that δ, κ, ε > 0 are for now any (small) positive number but can be specified later. δ 0 is the target error. We begin by giving a few notations. For the proof, we need to introduce the following probabilityEQUATIONwhere X ∼ N (0, I d ) and u is any unit vector in R d . Note that β(δ, κ) is independent of the choice of u by rotational invariance of Gaussian distribution. It is easy to check that P (x i ∈ C X (u, δ)) = P (y j ∈ C X (u, δ)) = β(δ, κ) for any i, j and any unit vector u.Step 1: General strategy. Our goal is to prove that w.h.p. we haveEQUATIONfor some δ 0 > 0 to be determined. This will entail thatQ -Q ⋆ 2 F ⩽ δ 0 d.Step 2: An upper bound on E F ( Q) . Since N is an ε-net of O(d), there existsQ ⋆ ε ∈ N such that ∥Q ⋆ ε -Q ⋆ ∥ F ⩽ ε. Note that by optimality of Q, one has F ( Q) ⩽ F (Q ⋆ ε ).We first upper bound the left hand side in (17) by upper bounding the expectation of F (Q ⋆ ε ) using the following result.Lemma 5. Let Q ∈ O(d), u ∈ S d-1 . We have:E [F (Q)] ⩽ 2nβ(δ, κ) c ′ d 2Bσ √ 6dδ + ρ(Q ⋆ -Q)/δ + 2e -B 2 /2 + e -d ,for any B 2 > 0, where for some matrix M , ρ(M ) is defined as its spectral radius.Lemma 5 (proved in next subsection) gives, for any B > 0:EQUATIONwhere we used ρ(Q⋆ -Q ⋆ ε ) ⩽ Q -Q ⋆ ε F⩽ ε in the above.Step 3: A lower bound on E [F (Q)] for any Q. W lower bound the right hand side in (17) using the following Lemma.Lemma 6. Let Q ∈ O(d), u ∈ S d-1 . We have, conditionally on the directions u 1 , . . . , u p ,E F (Q) u 1 , . . . , u p ⩾ 2C 1 β(δ, κ) p k=1 1 {∥(Q ⋆ -Q)u k ∥ 2 F >4δ+32σ}p .We recall that β(δ, κ) is defined in (16) here above. In the sequel, we denote by P U (resp. E U ) the probability (resp. expectation) over the directions u 1 , . . . , u p . Lemma 6 (proved in next subsection) gives thatEQUATIONNow, if we take δ 0 ⩾ 8δ + 64σ, we haveinf Q∈N ∥Q-Q ⋆ ∥ 2 F >δ0d E U p k=1 1 {∥(Q-Q ⋆ )u k ∥ 2 >4δ+32σ} (21) ⩾ inf Q∈N ∥Q-Q ⋆ ∥ 2 F >δ0d E U p k=1 1 {∥(Q-Q ⋆ )u k ∥ 2 >δ0/2} ⩾ inf Q∈N ∥Q-Q ⋆ ∥ 2 F >δ0d E U p k=1 1 ∥(Q-Q ⋆ )u k ∥ 2 > ∥Q-Q ⋆ ∥ 2 F 2d = p inf Q∈N ∥Q-Q ⋆ ∥ 2 F >δ0d P U ∥(Q -Q ⋆ )u 1 ∥ 2 > ∥Q -Q ⋆ ∥ 2 F 2d .Note that if Z ∼ N (0, I d /d), by rotational invariance of the Gaussian, one can always write Z = N u 1 where N = ∥Z∥ and u 1 = Z ∥Z∥ are independent and u 1 is uniform on the sphere. This yields∥Q-Q ⋆ ∥ 2 F d = E ∥(Q -Q ⋆ )Z∥ 2 = E N 2 E U [∥(Q -Q ⋆ )u 1 ∥ 2 ] = 1 × E U [∥(Q -Q ⋆ )u 1 ∥ 2 ].We can lower bound the right hand side of the above using a reverse Markov inequality, namely that P (X > E [X] /2) ⩾ E [X] /8 for any X such that 0 ⩽ X ⩽ 4 a.s. We apply this toX = ∥(Q -Q ⋆ )u 1 ∥ 2 and get that for all Q ∈ N such that ∥Q -Q ⋆ ∥ 2 F > δ 0 d, P U ∥(Q -Q ⋆ )u 1 ∥ 2 > ∥Q -Q ⋆ ∥ 2 F 2d ⩾ ∥Q -Q ⋆ ∥ 2 F 8d ⩾ δ 0 8 ,and via Equation ( 21), Equation ( 19) becomesEQUATION)Step 4: Uniform concentration of F (Q) around its mean. The remaining step is to control the concentration of F (Q) uniformly on N . This is given by the following.Lemma 7 (Concentration of F ). Let Q ∈ O(d) be fixed. Recall that q = p 3 , that v 1 , . . . , v q are i.i.d. uniformly sampled on the sphere S d-1 and that u 1 , . . . , u p are i.i.d. uniformly sampled in {v 1 , . . . , v q }. We have, for all λ > 0:P   F (Q) -E [F (Q)] ⩾ 4 √ 2λ 3 log(p) + λ + log(q) 2 +λ 2 9nβ(δ,κ) nβ(δ, κ) √ p   ⩽ 4e -λ + 2e -λ 2 . Hence, plugging λ = 2 log(|N |) > 1 (assuming |N | ⩾ 2) in Lemma 7, with probability at least 1 -6 |N | , we have sup Q∈N |F (Q) -E [F (Q)]| (23) ⩽ 8 √ 2 log(|N |) 3 log(p) + 2 log(|N |) + 9 log(p) 2 + 4 log(|N |) 2 9nβ(δ, κ) nβ(δ, κ)p -1/2 ⩽ c 4 d 2 log(1/ε) max(log(p), d 2 log(1/ε))nβ(δ, κ)p -1/2 (24) + c 5 d 2 log(1/ε) max(log(p), d 2 log(1/ε)) 2 p -1/2 .where we used log(|N |) ⩽ c 6 d 2 log(1/ε) in the above.Step 5: Wrapping things up. Putting together the control on deviation in ( 23), the upper bound ( 18) and the lower bound ( 22), one gets that with probability ⩾ 1 -6/|N |, for any B > 0:infEQUATION)If this lower bound is positive, we can conclude thatQ -Q ⋆ 2 F ⩽ δ 0 d, as desired.So far, the only constraints on our constants are (A1) δ 0 ⩾ 8δ + 64σ .While the noise parameter σ is fixed in this proof, we have the freedom to impose some constraints on ε (the granularity of the ε-net), δ (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 is what we shall do now.Recall that we are in a regime where we need to keepn in our minf that n tends to +∞ and d tends to +∞ with n but with d ⩽ log(n). We want to show that the positive term in (25) can dominate the others ; first, we would like to have an inequality of the formEQUATIONwhich is going to be satisfied if:(A2) C 1 > 8c 6 , (A3) δ 0 δ ⩾ c 7 √ dσB, (A4) δ 0 δ ⩾ c 8 dε, (A5) δ 0 ⩾ c 9 (e -B 2 /2 + e -d ), (A6) δ 0 ⩾ c 10 d 2 log(1/ε) max(log(p), d 2 log(1/ε))p -1/2, where c 7 , c 8 , c 9 , c 10 are large enough constants. Now,• (A2) is easily verified by choosing c 6 .• B only appears in (A3) and (A5). ( A5) is satisfied if we take δ 0 ⩾ 2c 9 e -d andB 2 = c 11 max(1, log(1/δ 0 )), transforming (A3) into δ0δ √ max(1,log(1/δ0)) ⩾ c 12 √ dσ;• ε appears in (A4) and can be taken as ε ⩽ δ0δ c8d for this condition to be satisfied. Combined with (A2), we can simply take ε ⩽ c 7 √ dσB/(c 8 d) for this condition to be 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) ε = c 16 d -1/2 σ , (A8) p 1/2 ⩾ c 13 σ -1 d 7/2 log(d/σ) 3 , (A9) δ = δ 0 , (A10) δ 2 0 max(1, log(1/δ 0 )) ⩾ c 15 √ dσ ,thereby transforming the condition that the RHS in Equation ( 25) is positive into:nβ(δ, κ) ⩾ c 16 d 2 log(1/ε) max(log(p), d 2 log(1/ε)) 2 p -1/2 √ dσ log( √ dσ) -1.The RHS of this inequality can be taken smaller than 1 by imposing that p is large enough (recall that p can be taken as large as desired). The final condition thus reads asnβ(δ, κ) ⩾ 1, which is itself satisfied if n ⩾ e c ′ d log(1/δ) (1 -e -d/16 ) -1 , since β(δ, κ) = P (x 1 ∈ C X (u 0 , δ), ∥x 1 ∥ ⩾ 1/κ) and P (x 1 ∈ C X (u 0 , δ)) ⩾ e -c ′ d log(1/δ) , while P (∥x 1 ∥ ⩾ 1/κ) ⩾ 1 -e -d/16 for (A12) κ 2 = 2 d .We are now going to use the low-dimensionality assumption d ≪ log(n) , since n ⩾ e c ′ d log(1/δ) (1e -d/16 ) will be verified for(A13) log(n) ⩾ c ′′ d log(1/δ) = c ′′ d log(1/δ 0 ) .Thus, under (A8-A13), Equation ( 25) is positive, and therefore we have that1 d Q -Q ⋆ 2 F ⩽ δ 0 .We introduce the (numerical) constants c, c ′ > 0 that verify, for all δ ′ ∈ (0, 1/4) that for x sampled uniformly on S d-1 and any u ∈ S d-1 we have 5 :exp -c ′ d log(1/δ ′ )) ⩽ P (x ∈ C(u, δ ′ )) ⩽ exp -cd log(1/δ ′ )) .The following lemmas are used to prove Lemma 6 and Lemma 5. 5 In our model, the probability P (x ∈ C(u, δ ′ )) can in fact be computed explicitly. For fixed d and n, the above probability is given by(1/2)P X 2 1 ⩾ (1 -δ) 2 (X 2 1 + . . . X 2 d )where the (Xi) are standard i.i.d. Gaussian variables. It is standard thatX 2 1 ∥X∥ 2 is distributed according to the beta distribution β(1/2, (d -1)/2), hence P x ∈ C(u, δ ′ ) = 1 2 P β(1/2, (d -1)/2) ⩾ (1 -δ) 2 = Γ(d/2) Γ(1/2)Γ( d-1 2 ) 1 (1-δ) 2 x -1/2 (1-x) (d-3)/2 dx ,which is indeed of order cδ d when δ is small.Proof of Lemma 5. We recall that for any i, j, P (x i ∈ C X (u, δ)) = P (y j ∈ C X (u, δ)) = β(δ, κ) for any unit vector u. Taking the expectation and developing the indicators, we haveE [F (Q)] = 1 p p k=1 n i=1 P x π ⋆ (i) ∈ C X (Qu k , δ) + P (y i ∈ C Y (u k , δ)) -2P x π ⋆ (i) ∈ C X (Qu k , δ)|y i ∈ C Y (u k , δ) P (y i ∈ C Y (u k , δ)) = 2β(δ, κ) p p k=1 n i=1 1 -P x π ⋆ (i) ∈ C(Qu k , δ), x π ⋆ (i) ⩾ 1/κ y i ∈ C(u k , δ), ∥y i ∥ ⩾ 1 + σ 2 /κ = 2nβ(δ, κ) 1 -P X ∈ C(Qu, δ), ∥X∥ ⩾ 1/κ Y ∈ C(u, δ), ∥Y ∥ ⩾ 1 + σ 2 /κ ,where X ∼ N (0, I d ), Y = Q ⋆ X + σZ with Z ∼ N (0, I d ) 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 Q is close to Q ⋆ . First, we separate the norm component from the direction component in the event {X ∈ C(Qu, δ), ∥X∥ ⩾ 1/κ}:P X ∈ C(Qu, δ), ∥X∥ ⩾ 1/κ Y ∈ C(u, δ), ∥Y ∥ ⩾ 1 + σ 2 /κ = P X ∈ C(Qu, δ) Y ∈ C(u, δ), ∥Y ∥ ⩾ 1 + σ 2 /κ P ∥X∥ ⩾ 1/κ|∥Y ∥ ⩾ 1 + σ 2 /κ ⩾ P X ∈ C(Qu, δ) Y ∈ C(u, δ), ∥Y ∥ ⩾ 1 + σ 2 /κ P (∥X∥ ⩾ 1/κ) . Now, we have y i ∈ C Y (u, δ) =⇒ x π ⋆ (i) ∈ C X (Q ⊤ u, δ + δ i (Q, u)) using Lemma 12, whereδ i (Q) = 2σ |⟨zi,(Q ⋆ ) ⊤ u⟩| ∥xπ⋆(i)∥ + ρ(Q ⋆ -Q), so that:P x π ⋆ (i) ∈ C(Q, δ) y i ∈ C(u, δ), ∥y i ∥ ⩾ 1 + σ 2 /κ = P x π ⋆ (i) ∈ C(Q, δ) y i ∈ C(u, δ), x π ⋆ (i) ∈ C(Q, δ + δ i (Q, u)), ∥y i ∥ ⩾ 1 + σ 2 /κ ⩾ E exp -c ′ d log 1 + 2σ |⟨z i , (Q ⋆ ) ⊤ u⟩| δ x π ⋆ (i) + ρ(Q ⋆ -Q)/δ ∥y i ∥ ⩾ 1 + σ 2 /κ ⩾ E exp -c ′ d log 1 + 2σB ′ δ x π ⋆ (i) + ρ(Q ⋆ -Q)/δ ∥y i ∥ ⩾ 1 + σ 2 /κ, |⟨z i , (Q ⋆ ) ⊤ u⟩| ⩽ B ′ × P |⟨z i , (Q ⋆ ) ⊤ u⟩| ⩽ B ′ ⩾ exp -c ′ d log 1 + 2κσB δ + ρ(Q ⋆ -Q)/δ (1 -P |⟨z i , (Q ⋆ ) ⊤ u⟩| > B )(1 -P x π ⋆ (i) ⩾ 1/κ . First, P x π ⋆ (i) 2 > d + 2 √ dt + t ⩽ e -t for any t > 0, so that if 1/κ 2 ⩾ 3d, P x π ⋆ (i) > 1/κ ⩽ e -1 3κ 2 +d .Then, |⟨z i , (Q ⋆ ) ⊤ u⟩| ∼ |N (0, 1)| since u us unitary, and thusP |⟨z i , (Q ⋆ ) ⊤ u⟩| > B ⩽ 2e -B 2 /2 ⩽ 2e -2 for B = 2, leading to:P x π ⋆ (i) ∈ C(Q, δ) y i ∈ C(u, δ), ∥y i ∥ ⩾ 1 + σ 2 /κ ⩾ exp -c ′ d log 1 + 2Bκσ δ + ρ(Q ⋆ -Q)/δ (1 -2e -B 2 /2 )(1 -e -1 3κ 2 +d ) ⩾ exp -c ′ d log 1 + 2N σ √ 6dδ + ρ(Q ⋆ -Q)/δ (1 -2e -B 2 /2 -e -d ) ,for κ 2 = 1/(6d). Using log(1 + x) ⩽ x and e -x ⩾ 1 -x for x ⩾ 0,P x π ⋆ (i) ∈ C(Q, δ) y i ∈ C(u, δ), ∥y i ∥ ⩾ 1 + σ 2 /κ ⩾ exp -c ′ d 2Bσ √ 6dδ + ρ(Q ⋆ -Q)/δ (1 -2e -B 2 /2 -e -d ) ⩾ 1 -c ′ d 2Bσ √ 6dδ + ρ(Q ⋆ -Q)/δ (1 -2e -B 2 /2 -e -d ) ⩾ 1 -c ′ d 2Bσ √ 6dδ + ρ(Q ⋆ -Q)/δ -2e -B 2 /2 -e -d .leading to1 -P x π ⋆ (i) ∈ C(Q, δ) y i ∈ C(u, δ), ∥y i ∥ ⩾ 1 + σ 2 /κ ⩽ c ′ d 2Bσ √ 6dδ + ρ(Q ⋆ -Q)/δ + 2e -B 2 /2 + e -d ,and thus to the desired upper bound onE [F (Q)].Proof of Lemma 7. We first begin by bounding all the terms that appear in the sum of F (Q). DefineA(u, Q) = |C X (Qu, δ)| -|C Y (u, δ)| , so that F (Q) = 1 p p k=1 A(u k , Q) 2 .Using Bernstein inequality [Vershynin, 2018, Theorem 2.8 .4], and writing β(δ, κ) = P x π ⋆ (i) ∈ C X (Qu, δ) (so that E [A(u, Q)] ⩽ nβ(δ, κ)), we have:P (|A(u, Q)| ⩾ t) ⩽ 2 exp - t 2 /2 nβ(δ, κ) + t/3 , so that P A(u, Q) 2 ⩾ nβ(δ, κ)t ⩽ 2 exp - nβ(δ, κ)t/2 nβ(δ, κ) + nβ(δ, κ)t/3 ⩽ 2 exp - t 4 + 2 exp - 3 nβ(δ, κ)t 2 .Now, we have:P ∃ℓ ∈ [q] , A(v ℓ , Q) 2 ⩾ nβ(δ, κ)t ⩽ 2 exp - t 4 + log(q) + 2 exp - 3 nβ(δ, κ)t 2 + log(q) = 4e -λ , for t = 4(3 log(p) + λ) + 4(log(q) 2 +λ 2 ) 9nβ(δ,κ). We now use MacDiarmid's inequality [Vershynin, 2018, Theorem 2.9 .1], by seeingF (Q) as F (Q) = f (u 1 , . . . , u p ), conditionally on the event ∀ℓ ∈ [q], A(v ℓ , Q) 2 ⩽ 4(3 log(p) + λ) + 4(log(q) 2 +λ 2 ) 9nβ(δ,κ) nβ(δ, κ) = B, to obtain P F (Q) -E [F (Q)|V ] ⩾ t ∀ℓ ∈ [q], A(v ℓ , Q) 2 ⩽ B ⩽ 2 exp pt 2 2B 2 ,where V = {v 1 , . . . , v q }, since the bounded difference inequality is then verified for constant 4B. Thus,P   F (Q) -E [F (Q)|V ] ⩾ √ 2 4(3 log(p) + λ) + 4(log(q) 2 +λ 2 ) 9nβ(δ,κ) nβ(δ, κ) √ p   ⩽ 4e -λ + 2e -λ 2 .The problem here lies in the fact thatE [F (Q)|V ] = E [F (Q)]may not always hold! Hopefully this is in fact the case:E [F (Q)|V ] = 1 pq p k=1 q ℓ=1 E (|C X (Qv ℓ , δ)| -|C Y (v ℓ , δ)|) 2 |u k = v ℓ = E (|C X (Qv, δ)| -|C Y (v, δ)|) 2 for any fixed v ∈ S d-1 = E [F (Q)] , concluding the proof.Proof of Lemma 6. Let ε > 0 to be determined later and k∈ [p] such that ∥(Q -Q ⋆ )u k ∥ > ε.We are going to show thatP x π ⋆ (i) ∈ C(Qu k , δ) y i ∈ C(u k , δ), ∥y i ∥ ⩾ √ 1 + σ 2 /κ, ∥(Q -Q ⋆ )u k ∥ > ε is small. Using Lemma 11, y i ∈ C(u k , δ) implies that x π ⋆ (i) ∈ C(Q ⋆ u k , δ + 2 σ∥zi∥ ∥xπ⋆(i)∥ ). Then, C(Qu k , δ) ∩ C(Q ⋆ u k , δ + 2 σ∥zi∥ ∥xπ⋆(i)∥ ) = ∅ provided that ∥Qu k -Q ⋆ u k ∥ 2 > 4(δ + σ∥zi∥ ∥xπ⋆(i)∥ ) using Lemma 8. Thus, if ∥Qu k -Q ⋆ u k ∥ 2 > ε, P x π ⋆ (i) ∈ C(Qu k , δ) y i ∈ C(u k , δ), ∥y i ∥ ⩾ 1 + σ 2 /κ, ∥(Q -Q ⋆ )u k ∥ > ε ⩽ P 4(δ + σ∥z i ∥ x π ⋆ (i) ) > ε ⩽ P 4σ∥z i ∥ x π ⋆ (i) > ε -4δ .We have P ∥z i ∥ 2 ⩾ 4d ⩽ e -d , andP x π ⋆ (i) 2 ⩽ d 2 ⩽ e -d/16 , so that if ε ⩾ 4δ + 32σ, we have P 4σ∥zi∥ ∥xπ⋆(i)∥ > ε -4δ ⩽ P ∥z i ∥ 2 ⩾ 4d + P x π ⋆ (i) 2 ⩽ d 2 ⩽ e -d + e -16d, leading toP x π ⋆ (i) ∈ C(Qu k , δ) y i ∈ C(u k , δ), ∥y i ∥ ⩾ 1 + σ 2 /κ, ∥(Q -Q ⋆ )u k ∥ > ε ⩽ e -d +e -d/16 ⩽ 1-C 1 ,where C 1 = 1/e + 1/e 1/16 > 0 is a numerical constant. This thus gives:E [F (Q)|U ] ⩾ 2C 1 β(δ, κ) p k=1 1 {∥(Q ⋆ -Q)u k ∥ 2 F >ε} p . Lemma 8 (Cone separation). For u, v ∈ S d-1 , C(u, δ) ∩ C(v, δ) ̸ = ∅ implies that ∥u -v∥ 2 ⩽ 8δ. Proof. Assume C(u, δ) ∩ C(v, δ) ̸ = ∅. Take w ∈ C(u, δ) ∩ C(v, δ):we can always assume that ∥w∥ = 1 by rescaling. Then, by triangle inequality, we have ∥u -v∥ ⩽ ∥u -w∥ + ∥v -w∥. Since w ∈ C(u, δ), ∥u -w∥ 2 = 2 -2⟨v, w⟩ ⩽ 2 -2(1 -δ) = 2δ, and the same is true for ∥v -w∥. Thisgives ∥u -v∥ ⩽ 2 √ 2δ.Lemma 9 (Probability that two cones are disjoint).EQUATIONF and let u be a random variable uniformly distributed over S d-1 . Then,P (C(Q ′ u, δ) ∩ C(Qu, δ) = ∅) ⩾ δ . Proof. Using the previous Lemma, P (C(Q ′ u, δ) ∩ C(Qu, δ) ̸ = ∅) ⩽ P ∥Qu -Q ′ u∥ 2 ⩽ 8δ . Let Z be the random variable Z = ∥Qu -Q ′ u∥ 2 . We have that E [Z] = ∥Q -Q ′ ∥ 2 F /d ⩾ 12δand Z ⩽ 4 almost surely. Thus, using a "reverse Markov" inequality,12δ ⩽ E [Z] = E [Z1 Z⩽8δ ] P (Z ⩽ 8δ) + E [Z1 Z>8δ ] P (Z > 8δ) ⩽ 8δP (Z ⩽ 8δ) + 4P (Z > 8δ) ⩽ 8δ + 4(1 -P (X ⩽ 8δ)) , that is P (X ⩽ 8δ) ⩽ 1 -δ, which concludes the proof.The following Lemma is easy and does require any proof. Lemma 10. For any u, δ ∈ (0, 1), we haveE [|C X (u, δ)|] = E [|C Y (u, δ)|] = nP (x 1 ∈ C(u, δ), ∥x 1 ∥ ⩾ 1/κ) = nβ(δ, κ) so that |C X (Qu, δ)| -|C Y (u, δ)| in the sum that de- fines F are all centered. |C X (u, δ)| and |C Y (u, δ)| are (correlated) binomial random variables of parameters (n, β(δ, κ)). Lemma 11. For any u ∈ S d-1 , i ∈ [n], we have y i ∈ C Y (u, δ) =⇒ x π ⋆ (i) ∈ C X ((Q ⋆ ) ⊤ u, δ + δ i ), where δ i = 2σ ∥zi∥ ∥xπ⋆(i)∥ and x π ⋆ (i) ∈ C X ((Q ⋆ ) ⊤ u, δ + δ ′ i ) =⇒ y i ∈ C Y (u, δ), where δ ′ i = 2σ ∥zi∥ ∥yi∥ .Proof. Let us prove the first assertion and assume that y i ∈ C Y (u, δ). We havey i = Q ⋆ x π ⋆ (i) +σz i ∈ C Y (u, δ), which writes as:⟨Q ⋆ x π ⋆ (i) + σz i , u⟩ ⩾ (1 -δ) Q ⋆ x π ⋆ (i) + σz i .Thus,⟨x π ⋆ (i) , (Q ⋆ ) ⊤ u⟩ ⩾ (1 -δ) Q ⋆ x π ⋆ (i) + σz i -σ⟨z i , (Q ⋆ ) ⊤ u⟩ ⩾ (1 -δ) Q ⋆ x π ⋆ (i) + σz i -σ∥z i ∥ ⩾ (1 -δ)( Q ⋆ x π ⋆ (i) -σ∥z i ∥) -σ∥z i ∥ ⩾ (1 -δ) Q ⋆ x π ⋆ (i) -2σ∥z i ∥ ⩾ (1 -δ -δ i ) Q ⋆ x π ⋆ (i) ,which is the desired result. The second assertion is proved exactly in the same way.Lemma 12. For anyu ∈ S d-1 , i ∈ [n], Q ∈ O(d), we have y i ∈ C Y (u, δ) =⇒ x π ⋆ (i) ∈ C X (Q ⊤ u, δ + δ i (Q, u)), where δ i (Q, u) = 2σ |⟨zi,(Q ⋆ ) ⊤ u⟩| ∥xπ⋆(i)∥ + ρ(Q ⋆ -Q).Proof. Assume that y i ∈ C Y (u, δ). As in the proof of the previous proposition, this reads as:⟨x π ⋆ (i) , (Q ⋆ ) ⊤ u⟩ ⩾ (1 -δ) Q ⋆ x π ⋆ (i) + σz i -σ⟨z i , (Q ⋆ ) ⊤ u⟩ ,and thus,⟨x π ⋆ (i) , Q ⊤ u⟩ ⩾ ⟨x π ⋆ (i) , (Q ⊤ -(Q ⋆ ) ⊤ )u⟩ + (1 -δ) Q ⋆ x π ⋆ (i) + σz i -σ⟨z i , (Q ⋆ ) ⊤ u⟩ ⩾ -x π ⋆ (i) ρ(Q -Q ⋆ ) + (1 -δ) Q ⋆ x π ⋆ (i) + σz i -σ⟨z i , (Q ⋆ ) ⊤ u⟩ ⩾ -x π ⋆ (i) ρ(Q -Q ⋆ ) + (1 -δ - |⟨z i , (Q ⋆ ) ⊤ u⟩| x π ⋆ (i) ) x π ⋆ (i) = (1 -δ -δ i (Q, u)) x π ⋆ (i) .This concludes the proof.E.1 Very-fast sorting-based estimator and equivalence with one step of Frank-WolfeWe have:∇f (D) = 2 DX ⊤ XX ⊤ X -2Y ⊤ Y DX ⊤ X + Y ⊤ Y Y ⊤ Y D ,for any bistochastic matrix D, leading to, forJ = 11 ⊤ n : ∇f (J) = 2 JX ⊤ XX ⊤ X -2Y ⊤ Y JX ⊤ X + Y ⊤ Y Y ⊤ Y J .For any permutation matrix P , we have since J ⊤ = J and JP = J:EQUATIONP (∀i, j ∈ [n], |⟨x i -x j , x⟩| > t∥x∥) ⩽ 2 exp(-t 2 /2 + 2 log(n)) , so that with probability 1 -2/n 2 , sup i,j |⟨x i -x j , x⟩| ⩽ 2 2 log(n)∥x∥. Similarly, with probability 1 -4/n 2 , sup i |⟨z i , Q ⋆ x⟩| ⩽ 2 log(n)∥x∥ and sup i |⟨Q ⋆ x i , z⟩| ⩽ 2 log(n)∥z∥.Then, we can write z i = z ′ i + z where z ′ i is Gaussian (its covariance matrix is the projection on the orthogonal of z) and independent from z. Thus,sup i |⟨z i , z⟩| ⩽ ∥z∥ 2 + sup i |⟨z ′ i , z⟩| ⩽ ∥z∥ 2 + 2 log(n)∥z∥ with probability 1 -2/n 2 .Thus, with probability 1 -8/n 2 and for σ ⩽ 1,sup i∈[n] |⟨x π(i) -x i , x⟩| × 1 n n i=1 σ 2 ⟨z i , z⟩ + σ⟨z i , Q ⋆ x⟩ + σ⟨Q ⋆ x i , z⟩ ⩽ 2 2 log(n)σ∥x∥ 2 log(n)∥x∥ + ∥z∥ 2 + 4 log(n)∥z∥Now, n∥x∥ 2 and n∥z∥ 2 are both χ 2 d random variables, so thatP max(|n∥x∥ 2 -d|, |n∥z∥ 2 -d|) > 2t + 2 √ dt ⩽ 4e -t .For t = 2( √ 2 -1)d, this leads to, with probability 4e -2( √ 2-1)d :∥x∥ 2 , ∥z∥ 2 ∈ [1/2, 3/2] d n .Thus, with probability1 -8/n 2 -4e -2( √ 2-1)d , sup i∈[n] |⟨x π(i) -x i , x⟩| × 1 n n i=1 σ 2 ⟨z i , z⟩ + σ⟨z i , Q ⋆ x⟩ + σ⟨Q ⋆ x i , z⟩ ⩽ 2σ 2 log(n)∥x∥ 2 2 log(n) + 3 d/n + 4 3 log(n) = C log(n)σ∥x∥ 2 ,for some numerical constant C, if n ⩾ d, leading to1 2n n i=1 ⟨x π(i) -x i , x⟩ 2 ⩽ C log(n)σ∥x∥ 2 .Now, if i ̸ = j are fixed, for t ⩽ 1, P 1 2 ⟨x i -x j , x⟩ 2 < t∥x∥ 2 = P N (0, 1) 2 < t ⩽ c √ t, for some constant c > 0.We are now going to upper bound the probability of the event A ="there exists I ⊂ [n] with |I| ⩾ αn and π a permutation such that (i) for all i ∈ I, π(i) ̸ = i, (ii) {i, π(i)} i∈I form disjoint pairs and (iii) for all i ∈ I, 1 2 ⟨x π(i) -x i , x⟩ 2 ⩽ β∥x∥ 2 ", for some constants α, β ∈ (0, 1) to be fixed later. Let I and π be fixed. Since π(i) ̸ = i, we have P 1 2 ⟨x i -x π(i) , x⟩ 2 > β∥x∥ 2 ⩽ 2e -β/2 , and using (ii) all pairs are independent, leading to:P (π, I satisfies (i)-(ii)-(iii)) ⩽ P ∀i ∈ I , 1 2 ⟨x i -x π(i) , x⟩ 2 > β∥x∥ 2 ⩽ c β .Thus, using a union bound over all possible I and π, we have that:P (A) ⩽ 2 n n n e -αβn/2+αn log(2) = e log(c √ β)αn+n log(n)+(1+α)n log(2) .Now, using what we have proved above, denoting B the event1 2n n i=1 ⟨x π(i) -x i , x⟩ 2 ⩽ C log(n)σ∥x∥ 2 , we have P (B) ⩾ 1 -8/n 2 -4e -2( √ 2-1)d . Let C be the event {ov(π, π ⋆ ) ⩽ 1 -δ}.NeurIPS Paper ChecklistQuestion: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [Yes] Justification: see supplementary materials for a notebook.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: All the details of training procedure and hyperparameters are listed in Section 3.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, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [No] Justification: the experiments are merely illustrative and due to the n 3 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 error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• 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 or the standard error of the mean. Justification: In preparing the submission, the authors did not track sufficient information on the computer resources. However, the resources needed to run experiments are minimal, as all can be run on a 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 or 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 as 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 or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?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 NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
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 a foundational research paper without any direct societal impact.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment 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 a 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 to 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 as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?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 a 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 to 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 a 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? 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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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 creators. 
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/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was 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. 
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 to 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 contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS 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. 
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 crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.• 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.38th Conference on Neural Information Processing Systems (NeurIPS 2024).again, see e.g.Laurent and Massart [2000]. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: The theoretical results are interesting for a relatively narrow audience of NeurIPS.
questions: questions: Why is the conical alignment loss not used in practical experiments? Is it because it gives poor practical performances?
limitations: limitations: not applicable.
paper_summary: paper_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$. 

The 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(
hat \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.

Next, 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.
strength_weakness: strength_weakness: 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.
At the very least it would be useful to recall the per iteration complexity.
questions: questions: The authors are kindly requested to answer to the above point. 

I noted the following typos:
1. line 139: is its probability -> if its probability.
2. line 279: envelop -> envelope.
limitations: limitations: The assumptions are clearly stated in each relevant result.
paper_summary: paper_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.
strength_weakness: strength_weakness: 1. Due to technical challenges, only guarantees for one step of the proposed algorithm is analyzed.
2. 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.
3. 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.
questions: 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.
2. Are there any negative information-theoretic results, i.e., lower bounds on the costs, for the Procrustes-Wasserstein Problem of the planted model?
3. Can there possibly be computational-statistical gaps for the problem?
limitations: limitations: The authors addressed most limitations of the work. Some additional ones are highlighted in Weaknesses and Questions sections.
paper_summary: paper_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.
strength_weakness: strength_weakness: + The title seems misleading. It is not clear about its relation with random graphs.
+ 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)
+ 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.
questions: 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:
+ 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?
+ 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? 
+ 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?
+ 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?
+ 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).
+ 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?
+ When Q*= I, could the authors compare the presented results with those in Kunisky and Niles-Weed (2022)?
+ 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?

---------
The rebuttal has addressed some of my concerns, I increase the score to 5.
limitations: limitations: It seems there is no discussion on the limitation.

Comments: title: Answers to follow-up
Reply to rebuttal
Response and clarifications
comment: Thank you again for your additional questions which we hope to clarify in the following. 

Let's start by recalling the two problems (GGA) and (PW). In both cases, we consider two point clouds written into matrices, namely $X = (x_1 | x_2 | .... | x_n)$ and $Y = (y_1 | y_2 | .... | y_n)$ with $x_i, y_i \in \mathbb{R}^d$. In this setting, (GGA) amounts to solving the minimization problem

$
P^*_{GGA} \in \mathrm{argmin}_{P \in \mathcal{S}_n} \Vert X^\top X P - P Y^\top Y \Vert_F^2
$

while (PW) amounts to solving

$
(P^*_{PW}, Q^*_{PW}) \in \mathrm{argmin}_{(P,Q) \in \mathcal{S}_n \times \mathcal{O}_d} \Vert QX - YP \Vert_F^2
$

Lemma 3 tells us that in (PW), it suffices to retrieve either $P^*_{PW}$ or $Q^*_{PW}$ to retrieve a very good guess of its respective counterpart.

If we understand you correctly, the key to both of your questions lies in the following "soft reformulation" of the optimization problem which was performed by (Grave, Joulin, Berthet, 2018) in their subsection **Convex relaxation**. The idea is to consider the following problem which is equivalent to (PW):

$
\text{max}_{P \in \mathcal{S}_n} \max_Q \text{tr}(Q X P^T Y^T) 
$

One has

$
\max_Q \text{tr}(Q X P^T Y^T) = \Vert X P^T Y^T \Vert_\star
$ 

where 
$\Vert A \Vert_\star$ 
denotes the trace norm (or nuclear norm) of a matrix 
$A$. 
If we put the singular values 
$\sigma_1, ..., \sigma_m$ 
of 
$A$ 
into a vector 
$v := (\sigma_1, ..., \sigma_m)$, 
then
$\Vert A \Vert_\star= \sum_i \sigma_i = \Vert v \Vert_1$. 
Since 
$\Vert A \Vert_F = \sqrt{\sum_i \sigma_i^2} = \Vert v \Vert_2$,
one can argue, using norm equivalence in
$ \mathbb{R}^m$, 
that the problems
$ \max_P \Vert X P^T Y^T \Vert_\star $ 
and 
$ \max_P \Vert X P^T Y^T \Vert_F^2 $ 
are very similar. [Note: We don't know a result to quantify how similar the solutions are, this is why this whole "soft reformulation" is more about giving intuition than providing rigorous results.]

Developing the square in $ \max_P \Vert X P^T Y^T \Vert_F^2 $ and omiting constant terms, this problem is further equivalent to

$ \max_P \mathrm{tr}( Y P X^T X P^T Y^T ) = \text{max}_P \mathrm{tr}( X^T X P^T Y^T Y P) $

Rewriting this as the minimum of the squared norm of a matrix distance, one obtains exactly (GGA). This whole reformulation process can also be reversed to move back, from (GGA) to (PW).


Now, let's move to answering your concrete questions:

**(1) about Lemma 1** 

It is true that in order to infer $Q^*$, one needs a good estimate of $P^*$. To obtain this estimate, we use the above "soft reformulation" and first solve (GGA) which is agnostic to $Q^*$. This is done via convex relaxation of $\mathcal{S}_n$ to the set of doubly stochastic matrices, followed by Frank-Wolve optimisation. This procedure is what Grave et al. call the initialisation to their algorithm; it is also the initialisation to our Ping-Pong steps. The doubly stochastic matrix obtained at convergence of Frank-Wolfe if our initial guess of $P^*$. Our one-step analysis of the algorithm lets us hope that this is indeed a good guess in general.

**(2) about GGA**

You are right that there is no retrieval of $Q^*$ in GGA. Our hope is that the "soft reformulation" can give a good idea where this $Q^*$ is hidden in the process. Since the geometric graph in GGA only depends on the scalar products between the vectors in $X$ and $Y$, our proof of lemma 1 explains in detail how an orthogonal transformation between the point clouds emerges when doing the problem reformulation (GGA) $\to$ (PW).
Thank you for your answer. I have some follow-up questions

**(1) about Lemma 1**
- The PW problem is non-convex for both (P, Q). However, in the proof of Lemma 1, line 119, it mention about the (sub)optimal $\pi*$ (which lead to the optimal $Q^*$). It is still unclear how to approximate such $\pi^*$ since the optimization problem involves both $(\pi, Q)$. Could you comment about it?

**(2) about GGA**
- Is it right that in GGA, we only care about the node corresponding $P^*$. Do we care about $Q^*$ in GGA? I confused about the role of $Q^*$ in GGA, do we really need to use $G$ in GGA?
I thank the authors for the detailed responses. I maintain my postive rating of the paper.
Thank you for your questions.

**(1)**
In GGA, whatever the orthogonal transformation applied, the scalar product is unchanged: $\langle Qx_i, Qx_j\rangle = \langle x_i,x_j\rangle$.
We thus only seek to retrieve the permutation, since the GGA problem is invariant by orthogonal transformation.
As for the role of edge weights, it is unclear for us what the question is: our point above is that the edge weights observed are invariant under orthogonal transformations.

**(2)**
Grave et al indeed use the same initialization.
Our paper distinguishes itself from their work in two ways. The first is in the methodology: the *amplification* step is more greedy and thus more efficient, while having the same computational cost. The second is that we propose a 1-step analysis, paving the way for a more general analysis.
I thank the authors for your explanation in the rebuttal. It addresses some of my concerns, and I increase the score to 5.

I have some quick questions as follows: 

**(1) For GGA (geometric graph alignment)**
- Could you elaborate with further details about applying an orthogonal map $Q^*$ to all the vectors leaves the scalar products invariant? I agree about the role of $P^*$, but it is still unclear about $Q^{*}$ in the GGA?
- Do we only try to recover the node correspondence? how's about the role of edge weights in the GGA?

**(2) For the proposed Ping-Pong algorithm**
- In Grave et al. (2019), they also consider the convex relaxation and leverage the Frank-Wolfe algorithm as in the proposed algorithm. Could you comment about it? It is better in case you could give some analysis/discussion and/or empirical illustration for them?

I will further adjust the score accordingly.
I thank the authors for clarifying these points. I concur that a more in-depth study of the ping-pong algorithm is of a great interest, but is likely complicated and would be deserving of a separate paper. The addition of the overall complexity is useful in my opinion.