- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper addresses the dependence of linearized optimal transport (LOT) on its reference measure. A single reference keeps each target's distance to the reference exact, but the distance between two targets can be distorted when they are far from the reference, and Prop. 1 makes this precise locally through curvature. MALOT uses several references (anchors) chosen by farthest point sampling. For each pair of measures it averages the squared per-anchor LOT distances with softmax weights that favor anchors close to either measure, so the weights change from pair to pair. For discrete plans that split mass, radial completion appends one scalar per anchor so that each block keeps the exact distance to its anchor. Theorem 2 bounds the error by the distances of the two measures to their nearest anchors plus a temperature term, for any finitely supported measures with exact reference plans, and Theorem 1 gives a smooth Riemannian counterpart. The validation measures stress against exact W2 on synthetic families and seven real datasets, and downstream classification on three of them, with single-reference LOT, concatenated LOT and sliced Wasserstein as baselines.
Critical strengths
- The idea is simple and, as far as I know, new. Previous works with several LOT references stack them into one long vector, while here each pair mostly relies on the references that are close to it. The four-point example in App. A.5 is a nice way to show why any fixed embedding has to distort W2 somewhere. The method only needs OT between the anchors and the data, and radial completion is a cheap and useful fix for discrete plans. This is the main reason I think the paper has value, since the dependence on the reference is a well known weakness of LOT and the idea is easy to adopt.
- The gains over single-reference LOT are consistent and carefully measured. Errors are computed against W2 itself without rescaling, the real data splits are by date, object or run, and the oracle experiment in Sec. 5.2 gives concatenation and MALOT the same references, so it isolates the effect of the weighting. Without radial completion, MALOT reduces the error of single-reference LOT on all seven real datasets, by roughly 10% to 33%, and the paper also reports the cases where things do not work.
Critical weaknesses
-
The theory does not really explain why the method works. Theorem 2 only relies on each block having the correct distance to its anchor, and then on the triangle inequality, as the authors say themselves in App. A. So the same bound would hold for a method that keeps only the distances to the anchors and throws away the transport maps. The paper actually has such a method, the anchor-radius control in Table 2, and it is much worse than MALOT. So what makes MALOT work seems to be the transport directions, and the theory says nothing about them. The bound is also loose in my opinion. On the crescents with 8 anchors it is larger than every distance in the data. Finally, the same kind of bound for a reference-based OT distance already appears in Mialon et al. (ICLR 2021, Lemma 3.1), along with an analysis of several references, and this work is not cited.
-
I think the experiments do not show that averaging over the anchors near the two endpoints is the right way to use them. When the plans from an anchor are maps, as for Gaussians or point clouds of the same size, each per-anchor LOT distance can only overestimate W2. In that case, simply taking the smallest of these distances can never do worse than the MALOT average, and there is nothing to tune. This is the setting of the rotating shapes experiment in Sec. 5.2 and of Stanford96. Using only the anchor closest to one of the two measures is another simple option. Aside from the anchor-radius control, none of these is compared, so the experiments mainly show that MALOT beats uniform concatenation. The evidence on the real datasets also seems limited. Radial completion, which is part of the default method, makes the error worse on several datasets, the accuracy gains over concatenation are small and given without error bars (on Fingering the gain is about one test frame, and concatenation is even better on ETH-80), and there are no runtimes.
Questions for authors
- What does Theorem 2 add compared to Lemma 3.1 of Mialon et al. (2021) and their analysis of several references? And which variant do you recommend by default, with or without radial completion?
- How does MALOT compare with the simpler options above, using the same anchors, i.e. the smallest per-anchor distance when the plans are maps, and the single closest anchor? Could you also give the spread across splits and some runtimes?
- I think a result that actually uses the transport directions would make the paper much stronger, for example a faster rate when the maps from the anchors are smooth.
6 comments
We appreciate your suggestions to compare Min-LOT and the single closest anchor. These controls help us assess the effect of endpoint weighting, and your observations about radial completion, accuracy, and runtime have helped us identify where the real-data evaluation needs further evidence.
Weakness 2. Matched baselines and real-data evidence
When Min-LOT has a pointwise advantage. Your common-source argument shows why the minimum is a strong baseline for deterministic maps. We agree that it applies to Stanford96's Gaussian transports and the equal-mass assignment plans in the original rotating-shape simulation. When the two reference transports are deterministic maps, applying them to the same anchor draw yields a feasible coupling. The per-anchor LOT separation is therefore at least the true distance . On the same bank, taking the minimum gives no larger pointwise absolute error than a weighted root mean square of the same separations. The minimum requires no temperature.
What changes under split plans. In the revised manuscript, we have updated the rotating multi-cluster comparison (Section 5.2) to use compressed anchors with eight equally weighted atoms and targets with 80 equally weighted atoms. The reference plans necessarily split mass in this setting. A barycentric block retains the conditional mean displacement, so for glued-coupling distance and uncompleted LOT separation ,
where and are the splitting variances. The variance term can exceed the coupling gap even though . With radial completion, the subtracted term is , so a split-plan LOT separation can still underestimate . Min-LOT selects the smallest separation, even if it is an underestimate. Let be that minimum for the chosen block variant. On those same blocks, MALOT has strictly smaller absolute error than Min-LOT exactly when .
Same-bank comparison with Min-LOT. We have added Min-LOT and Nearest-one at matched anchors and budgets (Tables 3–5, Appendices D.1–D.2). We use uncompleted blocks and compute raw stress against exact before embedding. On the rotating multi-cluster data, stress is 0.1094 for Min-LOT and 0.0508 for MALOT on the FPS bank, and 0.1141 versus 0.0595 on the oracle bank. Min-LOT underestimates 6,965 of 7,140 FPS pairs (97.55%) and 6,961 oracle pairs (97.49%). MALOT has strictly smaller absolute error on 6,498 FPS pairs and 6,791 oracle pairs. On the crescents, MALOT lowers full-pair stress at , including 0.0581 to 0.0173 at . The full-pair results nearly tie at , and Min-LOT gives lower stress on the 2,485 pairs with neither endpoint an anchor (0.0596 versus 0.0644).
Same-bank comparison with the single closest anchor. Nearest-one selects the anchor closest to either endpoint and uses that chart for both targets. Hard endpoint averages the squared separations from the two endpoints' nearest charts, distributing each endpoint's weight uniformly across ties. At positive temperature, MALOT can retain nearby charts beyond the closest ones. Comparing Nearest-one with Hard endpoint assesses the effect of including both endpoints' nearest charts. Comparing Hard endpoint with MALOT on the same blocks then assesses positive temperature. We have included an example in Appendix A.7 where the nearest chart gives 10, a nearby chart gives the exact distance of 8, and positive-temperature MALOT moves the estimate to 9.345.
Hard endpoint and MALOT give lower full-pair stress than Nearest-one in all six matched settings. On the crescents the values are 0.0185 for Hard endpoint, 0.0173 for MALOT, and 0.0326 for Nearest-one. Hard endpoint has lower full-pair stress than MALOT at crescent , while MALOT has lower stress at and on both multi-cluster banks. On the 2,211 non-anchor pairs at , Nearest-one has lower stress than MALOT (0.0326 versus 0.0342), and MALOT has lower maximum absolute error (0.0929 versus 0.1441).
Real-data follow-up. We are adding same-anchor comparisons with Min-LOT and Nearest-one on Stanford96 and oracle Concat LOT at matched anchors and on real datasets. The current Table 1 shows mixed effects of radial completion and small classification accuracy differences. We are checking the effect of radial completion across datasets, split-level accuracy on Fingering and ETH-80, and wall-clock costs by stage. We will share an update promptly once these real-data results are available.
We are grateful for your questions on prior bounds, split variability, and local rates. They helped us clarify the scope of our results.
Question 1. Relation to Mialon et al. and the recommended radial setting
Your comparison with Mialon et al. helped us clarify Theorem 2. For unregularized plans, their Lemma 3.1 bounds the single-reference glued distance error by twice the smaller anchor radius. Appendix B.2 gives a pairwise bound and a dataset-wide mean squared error bound for the uniform RMS of glued distances. In the revised manuscript, we have used this gluing to obtain a directional upper endpoint for . With a radius-based lower endpoint, it bounds either endpoint-weighted MALOT variant's error (Section 4.1 and Appendix A.6). Lemma 3 gives the uniform coverage and temperature guarantee for radially exact blocks.
Your question about the default helped us distinguish radial exactness in the coverage theorem from its empirical effect. We have specified uncompleted barycentric LOT blocks as the empirical default (Section 3.2, Algorithm 1). With optimal plans, completion restores exact anchor radii. It has no effect for deterministic maps and adds a nonnegative term to squared MALOT distances under split plans (Appendix C.1, Eq. (28)). It can reduce an underestimate or increase an overestimate. Holding banks, plans, and weights fixed on crescents, it raises stress from 0.0325 to 0.0383 at and lowers it from 0.0173 to 0.0046 at (Appendix D.3). In the current Table 1, completion raises stress on Caulobacter and ETH-80 and slightly lowers it on Fingering. Further real-data checks are in progress.
Question 2. Same-bank comparisons, variability across splits, and runtime
Your request helped us assess split variability and computational cost. On the same bank with deterministic maps, Min-LOT is pointwise at least as accurate as MALOT. With uncompleted blocks, MALOT has lower full-pair raw stress than Min-LOT and Nearest-one in all six matched settings, with non-anchor exceptions (Weakness 2, Tables 3–5). The matched Stanford96 comparisons are in progress.
We have added a five-fold held-out evaluation for each simulation (Appendix G, Table 10). Crescent rotations of each base shape stay together, and each multi-cluster fold holds out two targets per family. We select FPS anchors and calibrate the temperature on training data. The oracle uses fixed generating prototypes. Methods share anchors and uncompleted blocks within each fold, with test-pair raw stress against exact .
| Multi-cluster bank | MALOT | Min-LOT | Nearest-one | Hard endpoint |
|---|---|---|---|---|
| FPS | 0.0508 ± 0.0044 | 0.1116 ± 0.0047 | 0.0853 ± 0.0060 | 0.0613 ± 0.0019 |
| Oracle | 0.0584 ± 0.0035 | 0.1127 ± 0.0051 | 0.0812 ± 0.0023 | 0.0622 ± 0.0028 |
These are means and sample standard deviations. The training sets overlap, so the spread describes variation across these folds. On crescents, Min-LOT and Nearest-one have the lowest mean stress at and , respectively. MALOT has the lowest mean at .
We have reported setup, matrix assembly, and optional full classical MDS separately for both simulations (Table 2). In a separate single-threaded crescent benchmark using the same stored radii and blocks, median assembly takes 4.58 ms for Nearest-one, 40.95 ms for Hard endpoint, and 41.40 ms for MALOT (five interleaved runs, Appendix C.3). This benchmark excludes setup and MDS.
In Table 1, Fingering accuracy is 93.99% for MALOT versus 93.23% for Concat LOT. On ETH-80 it is 82.07% for Concat LOT versus 81.98% for uncompleted MALOT. We are checking split-level accuracy and timing real-data runs by stage. We will share the results promptly once available.
Question 3. A local recovery rate that uses transport directions
We appreciate your suggestion to quantify the benefit of directions under smooth maps. We have added a finite-pair bound for Eq. (10) in Appendix B.6. Under the smooth exact-map and geometric hypotheses of Theorem 1, we integrate LOT differential distortion along a piecewise smooth minimizing Wasserstein geodesic contained in the analysis region and apply the endpoint weights. For and , Eq. (25) gives
With bounded geometric constants, and give relative and absolute error. At the same temperature scale, Lemma 3 gives a general absolute bound for radially exact blocks.
We have also added a finite-plan ablation (Appendix D.3) that replaces each LOT separation by the absolute difference of its two block norms. Removing the angular term at fixed norms, plans, anchors, and weights raises raw stress at every crescent budget, from 0.0325 to 0.3636 at .
We are grateful for your assessment of the original coverage guarantee and for drawing our attention to Mialon et al. (2021). Your comments helped us clarify what the anchor radii guarantee and how transport directions improve the analysis of individual pairs.
Weakness 1. Coverage, transport directions, and prior work
What the original bound establishes. We agree that the original guarantee relies on radial exactness, the endpoint weights, and the triangle inequality. The same argument applies to scalar anchor radii, so it establishes uniform recovery as the covering radius and τlogK vanish. The proof leaves open how directional information affects a given pair. On the eight-anchor crescents, the uniform bound for radially completed MALOT is 1.3700, above the exact W2 diameter of 1.1544. In the revised manuscript, we have retained this guarantee as Lemma 3 (Appendix A.2, Eq. (17)) and made its scope explicit.
How the revised bound uses directions. We have revised Theorem 2 (Section 4.1, Eq. (13)) to use the alignment of the LOT displacements. Write Wij=W2(μi,μj) and rki=W2(ρk,μi). At a point drawn from anchor k, independently sample the two targets conditional on that point using the two optimal reference plans. This gluing gives a feasible target-pair coupling. With barycentric displacement blocks ϕki and ϕkj, its squared cost is
Gk2=rki2+rkj2−2⟨ϕki,ϕkj⟩.
The inner product measures how the displacements align. Feasibility gives Wij≤Gk, and the L2 triangle inequality gives Gk≤rki+rkj. Therefore the directional upper endpoint Uijdir=minkGk can tighten the radius-only upper endpoint Uijrad=mink(rki+rkj). Both intervals have the lower endpoint ℓij=maxk∣rki−rkj∣. Theorem 2 bounds the absolute error of either MALOT estimate D by
∣D−Wij∣≤max∣D−ℓij∣,∣D−Uijdir∣.
The bound uses the actual endpoint-weighted estimate and can improve its certificate even with the same anchor bank and weights. It is at most the corresponding radius-interval bound. For completed blocks it is also at most the original pair-specific coverage bound. For uncompleted blocks, the corresponding comparison with the coverage bound includes the computable difference between the two MALOT estimates. The certificate uses the reference plans already computed for MALOT and requires no additional target-pair transport solve (Appendix A.6).
What can be recovered at fixed coverage. To show what directions add when the radii agree, we have included a centered eight-atom example in Section 4.1 and Appendix A.6. Each distribution has the law of a uniformly random sign vector multiplied coordinatewise by positive scales. The target scales lie on a circle in a plane perpendicular to the line of anchor scales. Every target has the same radius vector at covering radius r>0, but distances between distinct targets range over (0,2r]. Any estimator based solely on the two radius vectors therefore has worst-case absolute error at least r. The optimal plans match signs, so every LOT separation equals the exact target-pair distance. Both MALOT variants and uniform LOT aggregation recover all the distances in this construction.
Bounds on the crescents. Your comparison with the data diameter underscored the importance of checking how conservative the bound is. We have added a comparison in Appendix D.3 of the maximum pairwise bounds and the observed maximum absolute errors at K=8.
For the uncompleted estimator used in the simulations, the directional interval strictly tightens the certificate on 902 of 2,775 pairs. Against exact W2, uncompleted MALOT has smaller observed absolute error than the pivot midpoint on 1,433 of these pairs. The maximum certificate remains substantially above the observed maximum error. In the separate fixed-weight control, replacing exact anchor-radius differences with the barycentric LOT separations reduces raw stress from 0.3549 to 0.0325 (Table 6).
We have added citations to Mialon et al. (2021) in the Introduction and Appendix A.6. Their shared-reference coupling is the basis for the directional upper endpoint. Our response to Question 1 explains how their bounds relate to the interval certificate for the endpoint-weighted estimator.