NOTE-1333: Alvarez-Melis et al. — OT with global invariances

Contribution

It gives one formulation for optimal transport between point sets whose spaces are related by an unknown global transformation from a stated class. It is a joint problem over the coupling Γ and a linear map P whose singular values lie in a Schatten ℓp ball. Prior OT–Procrustes methods are the special case of orthogonal P. Under either of two conditions the map can be eliminated in closed form, leaving a problem in Γ alone. For p = 2 that problem is exactly the Gromov–Wasserstein problem with cosine similarity and squared loss (Lemma 4.3), which ties the authors’ own GW method (LIT-1818) to the registration methods it set aside.

Key insight

There are two ways to make transport indifferent to an arbitrary transformation. One is to estimate the transformation together with the correspondence. The other is to compare only quantities the transformation cannot change, as GW does. For one class of transformations the two are the same problem. The paper’s phrase for its place between them is “a compromise between the classic formulation of OT that requires the spaces to be fully registered, and the GW distance, which completely forgoes explicit computation of distances across spaces” (p. 2). In every case the arbitrariness is one transformation for the whole space: “automatically derived representations such as word embeddings are typically fixed only up to some global transformations, for example, reflection or rotation” (p. 1).

Assumptions

• One unknown function f in a pre-specified class F relates the two spaces, “i.e., for which X = {x ∈ Rd | x = f (y), y ∈ Y}” (p. 4). The class is linear: F_p = {P ∈ ℝ^{d×d} : ‖P‖_p ≤ k_p}, a Schatten-norm ball (eq. 8, p. 4), with k_p chosen so the identity is inside (footnote 3).
• Squared Euclidean ground cost c(x, y) = ‖x − y‖² (p. 4), and for the main text m = n and d_x = d_y (footnote 2; App. A relaxes both).
• For the closed-form step (Lemma 4.1), one of: every P ∈ F is angle-preserving, ⟨Px, Py⟩ = ⟨x, y⟩; or ‖P‖_F = k for all P ∈ F and Y is ν-whitened, Y diag(q) Yᵀ = I_d (p. 5).
• For Lemma 4.3, cosine similarity with columns of X and Y normalised, “without loss of generality” (proof, p. 12).

Key results

The problem (§4, pp. 4–5)

• Eq. (7): min over Γ ∈ Π(p, q) and f ∈ F of ⟨Γ, C(X, f(Y))⟩.
• Eq. (9): with squared Euclidean cost and u_i = ‖x⁽ⁱ⁾‖², v_j = ‖Py⁽ʲ⁾‖², it becomes max over Γ, P of 2⟨Γ, XᵀPY⟩ − ⟨u, p⟩ − ⟨v, q⟩. It is not jointly concave, but concave in each variable with the other fixed (p. 5).
• Lemma 4.1 (p. 5): under either condition above, (9) is equivalent to (10): max over Γ and P ∈ F of ⟨XΓYᵀ, P⟩. The proof shows ⟨v, q⟩ is then constant in P (p. 11). Checked: for Y not whitened, ⟨v, q⟩ ranged from 1.75 to 27.59 over random P with ‖P‖_F = √5. After whitening it was 5 for every P.
• Lemma 4.2 (p. 5, proof p. 12): for M = UΣVᵀ, argmax_{‖P‖_p ≤ k} ⟨P, M⟩ = U diag(s) Vᵀ with ‖s‖_p ≤ k and sᵀσ = k‖σ‖_q, q the dual exponent. This is von Neumann’s trace inequality with Hölder; Lemma 3.1, the Procrustes solution UVᵀ, is its p = ∞ case. Checked: the closed form attains k‖σ‖_q for p = ∞, 2 and 1, and no random feasible P of 20,000 per case exceeded it. This is a weak check of maximality; the proof is the standard one.

The cases p = ∞ and p = 2 (§§4.1–4.2, pp. 5–6)

• p = ∞: with k = 1 and either condition of Lemma 4.1, F_∞ = O(d), “invariance to rotations and reflections” (p. 5). By duality, (10) becomes max_Γ ‖XΓYᵀ‖_* (eq. 13), a coupling that “maximizes the correlation of feature dimensions after transportation” (p. 6). The authors do not optimise (13) directly. They alternate (p. 6).
• p = 2: with F₂ = {‖P‖_F = √d}, (10) becomes max_Γ ‖XΓYᵀ‖_F (eq. 14).
• Lemma 4.3 (p. 6, proof p. 12): for cosine similarity and squared loss, the GW problem (15) and problem (14) are equivalent. The proof expands Σ (C^x_ik − C^y_jl)² Γ_ij Γ_kl into two terms fixed by the marginals and −2 Σ C^x_ik C^y_jl Γ_ij Γ_kl, and shows the latter sum equals ‖XΓYᵀ‖_F². Checked numerically to 10 decimal places on random unit-norm X, Y and a random coupling.
• A condition the statement leaves implicit. Lemma 4.3 links GW to (14). Problem (14) is the original transport problem (7) only through Lemma 4.1, and for p = 2 the matrices of F₂ are not angle-preserving, so that needs the whitening condition on Y. Lemma 4.3’s proof needs columns of equal norm. So “the choice p = 2 recovers … the Gromov-Wasserstein distance” (p. 4) holds for transport with a Frobenius-ball map exactly when Y is whitened and its columns have equal norm. Real embeddings are neither, unless preprocessed to be.
• p = 1 (App. B, p. 11): with Lemma 4.1’s conditions, F₁ again reduces to orthogonal matrices. The authors say this equivalence “is a consequence of the simplifying assumptions” (p. 11).

Optimisation (§4.3, App. E–F, pp. 6, 13)

• Alternate: an SVD for P, a Sinkhorn solve for Γ with cost −XᵀPY (pp. 5–6). Entropy is annealed, λ_t = αλ_{t−1}, with λ₀ = 1 and α = 0.95 in all experiments; “any sufficiently large choice of λ0 achieves the same objective” (p. 6). This is an observation, not a theorem.
• For large vocabularies, solve on the first k = 5,000 words and use the resulting P to initialise the full problem (App. F, p. 13).
• Footnote 7 (p. 13): “the order of the word embeddings leaks important—albeit noisy—correspondence information”, on which methods presented as fully unsupervised rely without saying so. This applies to the authors’ own two-stage scheme, and to LIT-1818’s first-K subset.

Experiments (§5, Figs. 2–4, Table 1, pp. 7–8)

• Synthetic (Figs. 2–3, p. 7): a 3-D cloud and a transformed copy. With an orthogonal transformation, ℓ∞-OT recovers the matching and classic OT does not (Fig. 2). Under noise, ℓ∞-OT beats ℓ2-OT when the truth is orthogonal “and vice versa” (p. 7). Both invariant methods beat an oracle that knows the transformation in the ℓ∞ case, which the authors attribute “to the added freedom of choosing P to overcome noise” (p. 7). Mean and s.d. over 5 repetitions. My check of the noiseless and σ = 0.1 cases (40 points, 10 random restarts) agreed: classic OT accuracy 0.05 and 0.03, ℓ∞-invariant OT 1.00 and 1.00.
• Word translation (Table 1, p. 8, P@1 with CSLS): ℓ∞-InvarOT: EN→ES 81.3, ES→EN 81.8, EN→FR 82.9, FR→EN 81.6, EN→DE 73.8, DE→EN 71.1, EN→IT 77.7, IT→EN 77.7, EN→RU 41.7, RU→EN 55.4, in 70 minutes. Gromov–Wasserstein (from LIT-1818): 81.7, 80.4, 81.3, 78.9, 71.9, 72.8, 78.9, 75.2, 45.1, 43.7, in 37 minutes. Self-learning + CSLS (Artetxe et al.): 82.3, 84.7, 82.3, 83.6, 75.1, 74.3, 79.2, 79.8, 48.9, 65.9, in 476 minutes. ℓ∞-InvarOT is compared, as the caption says, with Adv + CSLS without refinement (75.7 … 48.1, 643 minutes), and beats it on every pair. It beats GW on 6 of 10 directions. Self-learning beats it on 9 of 10, all but EN→FR.
• A discrepancy between the two papers. Table 1 here gives Adv + CSLS
  • Refine (Conneau et al.) 44.0 and 59.1 for EN→RU and RU→EN. LIT-1818’s Table 1 gives the same method 52.4 and 61.4. The other eight directions agree. I did not check which matches Conneau et al.
• Fig. 4 (p. 8): one run, EN→IT, 5K words: the objective and the accuracy are “strongly correlated” (p. 8).

Claims

id	claim	strength	support
C1	Under Lemma 4.1’s conditions, transport with an unknown map from a Schatten ℓp ball reduces to maximising the dual Schatten-q norm of XΓYᵀ over couplings	strong	Lemmas 4.1–4.2 with proofs (pp. 11–12); checked
C2	For p = 2 this is exactly GW with cosine similarity and squared loss	strong, with conditions	Lemma 4.3 with proof; checked. The link to the original transport problem needs whitened Y with equal-norm columns
C3	Prior OT–Procrustes methods are the p = ∞ case	strong	by construction (§§2, 4.1)
C4	Annealing the entropy removes sensitivity to initialisation and to λ	weak	observation in one experimental setting (p. 6); no restarts reported for the word task
C5	ℓ∞-invariant OT matches the state of the art on word translation at a fraction of the cost	moderate	Table 1; level with GW, behind self-learning on 9 of 10 directions, single runs
C6	ℓ∞-OT recovers correspondences under an orthogonal transformation where classic OT fails	strong	Figs. 2–3, 5 repetitions; reproduced
C7	The order of embedding files leaks correspondence information that “fully unsupervised” methods use	moderate	stated in footnote 7 (p. 13); argued, not measured

Method

Algorithm 1 (App. E, p. 13): initialise P in F_p from a random matrix’s SVD; repeat (i) pairwise costs between X and PY, (ii) Sinkhorn for Γ, (iii) SVD of XΓYᵀ and P = U diag(s) Vᵀ with s ∝ σ^{q−1} rescaled to ‖s‖_p = k_p, (iv) λ ← max(λη, λ_min); stop when the objective converges.

Concepts

• Unregistered spaces — spaces with “no a priori meaningful notion of distance between them” (p. 4); the global correspondence is unknown.
• Invariance class F_p — the Schatten ℓp ball of linear maps (eq. 8). p = ∞ gives orthogonal maps, p = 1 encourages low rank, intermediate p interpolate (p. 4, Fig. 1).
• Barycentric mapping — XΓ, the source points moved by the coupling; (9)‘s first term measures its agreement with PY (p. 5).

Connections

• Its p = ∞ case is Rangarajan et al. 1997 (Softassign Procrustes), Zhang et al. 2017b and Grave et al. 2018 (Wasserstein Procrustes) (§2, p. 2). Grave et al.’s convex initialisation is a hybrid of the p = 2 and p = ∞ cases (footnote 1).
• Its p = 2 case is LIT-1818’s GW alignment (Lemma 4.3).
• LIT-1808 extends the registration class past linear maps, to hyperbolic neural networks, because the arbitrariness there is not a global isometry.

Bearing on the record

• QUESTION-130 and THEORY-1140: the middle term of the three-way distinction, confirmed in the text. The “Why this is here” sets three kinds of arbitrariness apart. This paper treats as arbitrary one global transformation of a whole space, drawn from a stated class: “we assume there exists an unknown function f in a pre-specified class F which characterizes the global correspondence between spaces” (p. 4). The same P acts on every point. GW (LIT-1818) instead removes a single isometry of each space by never comparing across spaces, and Lemma 4.3 shows the two coincide for one class. Neither has a frame per node. In THEORY-1140 each entity’s frame changes independently and the relations transform as Tᵢⱼ ↦ gᵢTᵢⱼgⱼ⁻¹, so invariant information lives on cycles. Here the freedom is a single element of a group, applied to all points at once. It has no cycles to carry anything, and a fitted P gives no holonomy. Reading a fitted orientation as path dependence therefore confuses the global freedom here with the local one there. The distinction holds as the exchange drew it.
• CLAIM-148: a worked instance of identification up to a stated group. CLAIM-148 says a factorization is identified up to invertible maps, and that penalties narrow the gauge, weight decay to rotations. Here the analyst states the gauge as F_p and estimates it jointly with the correspondence. Lemma 4.2 shows how the choice of p fixes the solution’s spectrum. The class is chosen. Nothing in the paper tests whether the data’s ambiguity is that class (p. 4: “Naturally, the choice of F should be informed by the application domain”).
• CLAIM-113: consistent. The invariance class F_p and the objective’s invariants define each other exactly. (13) and (14) are unitarily invariant norms of XΓYᵀ, so they are unchanged by an orthogonal map of either space.
• CASE-185: the same identification threat applies. If Y has a symmetry realised by an orthogonal map, QY = Y with a permutation of its columns, then P and PQ give the same cost with permuted couplings. The global-invariance method inherits THEORY-1133’s ambiguity for every symmetry inside its class. Footnote 7 is a second point for the case: correspondence information can enter through the order or selection of items, and has to be controlled for.
• CLAIM-135: it supports the reconstruction step only. The paper’s accuracy is measured against dictionaries and says nothing about constitution.
• An instruction for ML practice is present (the annealing schedule, the two-stage scaling, the choice of p by domain). That belongs to the Anthology of the SOTA; the LIT carries the anthology-candidate flag.

Limitations

• Single runs on the word task; no restarts or variances reported.
• “Robust to λ” is shown by the annealing scheme’s behaviour on these tasks, not proved.
• The GW equivalence holds under conditions that the paper states in two separate places and real embeddings do not meet without preprocessing.
• The invariance class is assumed, not inferred. If the spaces differ by a non-linear warp, as LIT-1808 finds for hyperbolic embeddings, no p helps.
• Table 1’s EN–RU entries for Conneau et al. disagree with the companion paper’s.
• The figures’ data did not survive extraction; I used captions, Table 1 and my own reproduction.

Open questions

• For p strictly between 1 and ∞, with neither condition of Lemma 4.1 holding, how much does the Frank–Wolfe solution differ from the closed-form one? The paper mentions the route (p. 5) and does not run it.
• Can the invariance class be selected from data, for instance by comparing the fitted objective across p, without labelled pairs?