Distributionally Robust Optimization over Incomparable Spaces

Jieling Shi; Junyu Chen; Yong Sheng Soh

REVIEW

Distributionally Robust Optimization over Incomparable Spaces

Junyu Chen, Jieling Shi, Yong Sheng Soh

Optimization and Control · Submitted 1 Nov 2026 · 43 references

Pith's verdict: A genuinely new DRO formulation using Gromov-Wasserstein distance for incomparable spaces; well-executed theory and honest about its computational limitations. This paper deserves a serious referee.

T0 · AI review

How this review was made: An AI referee (deepseek/deepseek-v4-flash) read the paper on November 4, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

T0 AI review An AI read the paper and answered a fixed list of questions.
T1 Audit Automatic checks that the references and files the paper relies on exist and match.
T2 Compute The paper's code or calculations re-run with the same results.
T3 Formal statement The claims written out in a formal math language a computer can read.
T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 2 major objections · 6 minor · Ask about this paper · The compiled record · Read the full review →

Challenge this review Comment (0) Read on arXiv ↗

Cite ▾

arXiv ID2611.01557 (version 1)

Pith ID45LPNV4I, Pith's permanent record of this paper and its review

CitationJieling Shi, Junyu Chen, Yong Sheng Soh. "Distributionally Robust Optimization over Incomparable Spaces." arXiv:2611.01557 (2026). https://pith.science/paper/45LPNV4I

Cite this reviewBibTeX for Pith's review of this paper

Claim paper

Why Pith says this

Highlight any text to comment on it.

Editor's note

read the letter

This paper introduces a distributionally robust optimization formulation where the ambiguity set is defined via Gromov-Wasserstein distance, allowing the reference distribution and the decision space to be on different metric spaces. That is a real gap in the Wasserstein-DRO literature, and the authors fill it cleanly. The theoretical unification of CVaR, group DRO, robust k-median, and k-median with outliers as special cases is convincing and demonstrates the framework's breadth. The computational approach using DNN relaxation and facial reduction is correctly derived, and strong duality is proven under a strictly feasible point (Theorem 3.3). The experiments on clustering and graph k-median show concrete improvements over baselines (srGW, empirical optimization, WDRO).

The authors are honest about the limitations: the inner GW problem is NP-hard, the DNN relaxation provides only an upper bound with no tightness guarantee, and they do not provide finite-sample guarantees. They also do not release code. These are real, but they are stated transparently and do not undermine the validity of the central contribution.

Soft spots in proportion: (i) Scalability: the experiments use m=n=10, and the SDP-based relaxation does not scale to large problems. The paper does not discuss this limitation explicitly, but practical applicability is currently limited to small metric spaces. (ii) No finite-sample or out-of-sample guarantees: the paper acknowledges this, but given the DRO framing, its absence is a limitation for data-driven use. (iii) Code is not provided, which reduces reproducibility. (iv) The assumption that the metrics d_X and d_Y capture the relevant structural similarity is load-bearing; the paper states this clearly.

Overall, the paper is a solid theoretical contribution that opens a new direction. The writing is clear and precise. I would bring it to reading group and cite it in future work on DRO over incomparable spaces. This deserves serious peer review and likely acceptance after minor revisions (e.g., adding a discussion on scalability, and ideally releasing code).

Referee report

Significance

The paper bridges two active research areas—distributionally robust optimization and optimal transport over incomparable spaces—and introduces a genuinely new DRO model. The connections to CVaR, group DRO, robust k-median, and k-median with outliers are not merely formal: they show that the GW-DRO framework unifies problems that were previously studied independently, which is a conceptual contribution. The computational pipeline (DNN relaxation plus facial reduction) is correctly derived from prior GW relaxation work and is honest about its limitations (upper bound, no guaranteed tightness). If the formulation were adopted, it could allow decision-makers to incorporate structural information from a source space into a robust optimization on a different target space, a scenario that arises in domain adaptation, cross-modality learning, and network design. The experiments, while small-scale, provide proof-of-concept evidence that the method can give better decisions than alternative approaches under sampling or adversarial perturbations.

Major objections (2)

[Section 3, Eq. (31) and subsequent discussion] The paper states that the DNN relaxation (31) provides an upper bound for the inner worst-case problem and that Corollary 3.2 offers a check for global optimality, but no characterization of when the relaxation is tight for the DRO context is given. Given that the overall optimal value of (GW-DRO) is only an upper bound when the DNN gap is present, the authors should discuss, even qualitatively, the conditions under which the DNN relaxation can be expected to be tight (e.g., the numerical evidence in prior GW relaxation papers [7,34] and whether those conditions carry over to the DRO setting). A brief comment on how the gap may depend on ρ, the metric structures, or the cost function would improve the reader's understanding of the method's reliability.
[Section 4, numerical experiments] Both experiments are on very small instances (|X|=10, |V|=14). While the paper does not claim scalability, the computational pipeline involves solving SDPs (via MOSEK/SCS) whose size scales as O(mn) after facial reduction. The paper would benefit from a brief discussion of the practical computational complexity (SDP cone dimensions for the reduced problem (35), typical solver times for the reported instances) and an indication of the largest problem sizes that could reasonably be tackled with current SDP technology. This would help readers assess the practical applicability of the method beyond toy problems.

Minor objections (6)

[End of Section 1.2, line “graph representation learning [37, 38]”] The references [37] and [38] appear to be the same author group (Vincent-Cuaz et al.) with different years; please verify that the intended works are distinct and correctly cited.
[Section 2.1, Figure 1 caption] The caption mentions 'histogram axes show normalized arc positions' but the figure itself is rendered as a schematic with bars and curves; add a brief explanation of how the normalized arc positions are computed (e.g., whether arc length on the source line is mapped linearly to the target spiral's arc length).
[Section 3, after Eq. (28)] The text says 'Then Z = zz^T ⇔ W ⪰ 0 and rank(W) = 1.' For completeness, note that the equivalence also requires that the bottom-right entry of W is 1, which is enforced by the definition of W.
[Section 3.2, line 'the set \{ W \in S^{mn+1}_+ : \langle H^T H, W \rangle = 0 \}'] The trace inner product ⟨H^T H, W⟩ = 0 forces range(W) ⊆ ker(H), but the statement 'W ⪰ 0 and HW = 0 are equivalent to ⟨H^T H, W⟩ = 0' is correct only if H^T H ⪰ 0, which holds. Consider adding a short justification or citing a standard linear algebra fact.
[Section 4.2, line 'we use the first N observations'] It is stated that 'for each sample size N ∈ {100,200,300,400,500}, we use the first N observations' from a sample of 500 drawn from p. This means results at different N are not independent (the N=100 sample is a subset of the N=200 sample). For statistical validity the authors should either clarify that this is intentional (e.g., to study the effect of sample size without re-drawing), or note that standard errors may be underestimated.
[General] The paper uses 'minimax' throughout; the standard hyphenated form is 'min–max' or simply 'minimax' (acceptable). Consistency would be improved by using one form throughout. Also, check for a small number of missing articles (e.g., 'the GW-DRO problem' vs. 'GW-DRO problem'); these do not affect comprehension.

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

A new DRO formulation uses the Gromov-Wasserstein distance to define ambiguity sets over incomparable metric spaces, unifying several existing optimization problems as special cases.

The reading

Decision-makers often face uncertainty about the true distribution of input data. Standard distributionally robust optimization (DRO) uses optimal transport distances to define an ambiguity set of plausible distributions around an observed reference. But this requires that the reference data and the decision space are the same space. This paper introduces a DRO formulation that works when the reference data (a source distribution) lives on a different metric space from the outcomes on which decisions are evaluated. The key idea is to use the Gromov-Wasserstein (GW) distance instead of the classical Wasserstein distance. The GW distance compares metric spaces by evaluating how much a coupling distorts pairwise distances within each space, requiring only that both spaces have a metric structure, not that they are the same space. The authors show that several existing optimization formulations, including conditional value-at-risk minimization, group DRO, robust graph k-median, and k-median with outliers, are special cases of their framework. This demonstrates the modeling power of the GW-based ambiguity set. Computationally, the inner worst-case problem is a non-convex quadratically constrained quadratic program because the GW distance itself is defined via a quadratic objective. The authors use a doubly nonnegative (DNN) relaxation to obtain an upper bound, and apply facial reduction to recover strong duality. Numerical experiments on clustering and graph k-median show that the GW-DRO approach outperforms simpler baselines like semi-relaxed GW projection followed by Wasserstein DRO.

Extended reading notes

Core claim

The paper provides a new distributionally robust optimization formulation in which ambiguity sets are defined through the Gromov-Wasserstein distance (Equation 6-7, problem GW-DRO), enabling robust decision-making when the reference data distribution and the decision space are incomparable metric spaces. The formulation is stated in the abstract as: 'we provide a new DRO formulation in which ambiguity sets are defined through the Gromov-Wasserstein distance, which is an extension of OT to pairs of distributions residing in incomparable spaces.' (sentence b4).

Load-bearing premise

The paper assumes that the source space Y and target space X are both metric spaces (stated in conditions b46-b47) and that a structural similarity between them makes the Gromov-Wasserstein distance a meaningful measure of closeness between distributions across spaces (b52). This depends on the choice of metrics d_X and d_Y capturing the relevant structure for knowledge transfer. If the metrics are misaligned with the actual relationship between the spaces, the GW ambiguity set may not contain distributions that are genuinely plausible. A more specific load-bearing assumption is that the DNN relaxation (31) provides a sufficiently tight upper bound for the inner worst-case problem in practice; the paper provides a check in Corollary 3.2 but no guarantee of tightness.

Original abstract

Distributionally robust optimization (DRO) provides a principled framework for making decisions under uncertainty when the underlying distribution may be incorrectly specified. A widely used approach builds on ideas from optimal transport (OT) as a means of measuring differences between distributions. However, this depends on these distributions residing in the same space. In certain settings, the reference data distribution we have and the space on which we make our decision may be different, which renders classical OT techniques impossible. In this paper, we provide a new DRO formulation in which ambiguity sets are defined through the Gromov-Wasserstein distance, which is an extension of OT to pairs of distributions residing in incomparable spaces. We show that several seemingly unrelated optimization formulations, including conditional value-at-risk minimization, group distributionally robust optimization, robust graph $k$-median, and $k$-median with outliers, can be recovered as special cases of our formulation. We describe the computational aspects of solving the proposed formulation based on the doubly-nonnegative relaxation. Last, we illustrate the framework through experiments on clustering over incomparable spaces and stochastic graph $k$-median.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-11-03: 1 request, 6,241 input tokens.

What the abstract itself states, as probabilities: claims first 0.09 · states limitation 0.17 · human participants 0.03 · controlled comparison 0.03 · randomized assignment 0.02 · states quantitative result 0.04 · compares with prior results 0.34 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; show every role.

Distributionally robust optimization (DRO) provides a principled framework for making decisions under uncertainty when the underlying distribution may be incorrectly specified. A widely used approach builds on ideas from optimal transport (OT) as a means of measuring differences between distributions. However, this depends on these distributions residing in the same space. In certain settings, the reference data distribution we have and the space on which we make our decision may be different, which renders classical OT techniques impossible. In this paper, we provide a new DRO formulation in which ambiguity sets are defined through the Gromov-Wasserstein distance, which is an extension of OT to pairs of distributions residing in incomparable spaces. We show that several seemingly unrelated optimization formulations, including conditional value-at-risk minimization, group distributionally robust optimization, robust graph $k$-median, and $k$-median with outliers, can be recovered as special cases of our formulation. We describe the computational aspects of solving the proposed formulation based on the doubly-nonnegative relaxation. Last, we illustrate the framework through experiments on clustering over incomparable spaces and stochastic graph $k$-median.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	Distributionally robust optimization (DRO) provides a principled framework for making decisions under uncertainty when the underlying distribution may be incorrectly specified.	background 1.00	0.05	0.03	asserted 0.97
s1	A widely used approach builds on ideas from optimal transport (OT) as a means of measuring differences between distributions.	background 1.00	0.04	0.02	asserted 1.00
s2	However, this depends on these distributions residing in the same space.	background 0.47	0.05	0.02	asserted 1.00
s3	In certain settings, the reference data distribution we have and the space on which we make our decision may be different, which renders classical OT techniques impossible.	gap 0.66	0.06	0.03	asserted 0.81
s4	In this paper, we provide a new DRO formulation in which ambiguity sets are defined through the Gromov-Wasserstein distance, which is an extension of OT to pairs of distributions residing in incomparable spaces.	contribution 0.92	0.95	0.57	asserted 1.00
s5	We show that several seemingly unrelated optimization formulations, including conditional value-at-risk minimization, group distributionally robust optimization, robust graph $k$-median, and $k$-median with outliers, can be recovered as special cases of our formulation.	result 0.71	0.94	0.39	asserted 1.00
s6	We describe the computational aspects of solving the proposed formulation based on the doubly-nonnegative relaxation.	method 0.93	0.91	0.03	asserted 0.95
s7	Last, we illustrate the framework through experiments on clustering over incomparable spaces and stochastic graph $k$-median.	contribution 0.73	0.94	0.06	asserted 0.99

What kind of paper the classifier reports this is: method or tool 1.00 · evidence from proof or derivation 0.74.

What was examined, and what was not

sources read

arXiv listing abstract v1

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

Figures

**Figure 1.** Distributions on source and target curves. Dot areas and bar heights represent proba

**Figure 2.** Source and target spaces for the clustering experiment. (a) Source population probabil

**Figure 3.** Comparison of GW-DRO and srGWon the clustering task over incomparable spaces. (a)

**Figure 4.** Visualization of graphs. The graph with |V | = 14 vertices and vertex size proportional to probabilities. The adversarial distribution q is obtained by redistributing the probability weights of p among the branches. Edges indicate adjacency; their lengths in the drawing do not represent the metric d. We compare (GW-DRO) with empirical optimization and WDRO. For all three methods, θ = C, Θ = {C ⊆ V : |C| = 3}, and fθ(v) = fC(v) := d(v, C). In (GW-DRO), we take X = Y = V , dX = dY = d, and source distribution µbY,N . Empirical optimization solves (39) with p replaced by µbY,N . WDRO…

**Figure 5.** Comparison among empirical optimization, (GW-DRO), and WDRO on stochastic graph

**Figure 6.** The relation between stochastic graph k-median using (GW-DRO) and robust graph k-median. The optimal value of (GW-DRO) is nondecreasing in the radius ρ and equals the optimal value of robust graph k-median when ρ ≥ ρ(µbY,500). The horizontal dashed line gives the robust graph k-median value, and the vertical dotted line denotes the radius threshold. Points give computed upper bounds, and vertical bars span the corresponding lower and upper bounds. The star marks the evaluation at the radius threshold, and the subfigure zooms in near the threshold. References [1] David Alvarez-Melis…

Figures reproduced from arXiv:2611.01557 by the authors.

References

Works cited (43)

[1]

David Alvarez-Melis and Tommi Jaakkola. Gromov–Wasserstein alignment of word embedding spaces. InProceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 1881–1890. Association for Computational Linguistics, 2018

View on Pith 2018
[2]

Barbara Anthony, Vineet Goyal, Anupam Gupta, and Viswanath Nagarajan. A plant location guide for the unsure: Approximation algorithms for min-max location problems.Mathematics of Operations Research, 35(1):79–101, 2010

View on Pith 2010
[3]

Immanuel M. Bomze and Etienne de Klerk. Solving standard quadratic optimization prob- lems via linear, semidefinite and copositive programming.Journal of Global Optimization, 24(2):163–185, 2002

View on Pith 2002
[4]

Jon M. Borwein and Henry Wolkowicz. Facial reduction for a cone-convex programming problem.Journal of the Australian Mathematical Society, 30(3):369–380, 1981

View on Pith 1981
[5]

Jens Breitung, Timo Gervens, and Julius P¨ orzgen. Graph distortion distances, gro- mov–hausdorff and the hardness of gromov–wasserstein.arXiv preprint arXiv:2610.16926, 2026

View on Pith Pith review arXiv 2026
[6]

Kai Cao, Yiguang Hong, and Lin Wan. Manifold alignment for heterogeneous single-cell multi- omics data integration using Pamona.Bioinformatics, 38(1):211–219, 2022. 21

View on Pith 2022
[7]

Junyu Chen, Binh T. Nguyen, Shang Hui Koh, and Yong Sheng Soh. Semidefinite relaxations of the Gromov–Wasserstein distance. InAdvances in Neural Information Processing Systems, volume 37, 2024

View on Pith 2024
[8]

Liqun Chen, Zhe Gan, Yu Cheng, Linjie Li, Lawrence Carin, and Jingjing Liu. Graph optimal transport for cross-domain alignment. InProceedings of the 37th International Conference on Machine Learning, volume 119 ofProceedings of Machine Learning Research, pages 1542–1553. PMLR, 2020

View on Pith 2020
[9]

Erick Delage and Yinyu Ye. Distributionally robust optimization under moment uncertainty with application to data-driven problems.Operations Research, 58(3):595–612, 2010

View on Pith 2010
[10]

Pinar Demetci, Rebecca Santorella, Bj¨ orn Sandstede, William Stafford Noble, and Ritamb- hara Singh. SCOT: Single-cell multi-omics alignment with optimal transport.Journal of Computational Biology, 29(1):3–18, 2022

View on Pith 2022
[11]

Pinar Demetci, Quang Huy Tran, Ievgen Redko, and Ritambhara Singh. Breaking isometric ties and introducing priors in Gromov–Wasserstein distances. InProceedings of the 27th In- ternational Conference on Artificial Intelligence and Statistics, volume 238 ofProceedings of Machine Learning Research, pages 298–306. PMLR, 2024

View on Pith 2024
[12]

Rui Gao, Liyan Xie, Yao Xie, and Huan Xu. Robust hypothesis testing using Wasserstein uncertainty sets. InAdvances in Neural Information Processing Systems, volume 31, pages 7902–7912, 2018

View on Pith 2018
[13]

Anupam Gupta, Benjamin Moseley, and Rudy Zhou. Structural iterative rounding for gener- alizedk-median problems.Mathematical Programming, 212:581–634, 2025

View on Pith 2025
[14]

Gurobi Optimization, LLC.Gurobi Optimizer Reference Manual

View on Pith
[15]

Di Hou, Tianyun Tang, and Kim-Chuan Toh. RiNNAL+: A Riemannian ALM solver for SDP-RLT relaxations of mixed-binary quadratic programs.arXiv preprint arXiv:2507.13776, 2025

View on Pith Pith review arXiv 2025
[16]

Guillaume Houry, Jean Feydy, and Fran¸ cois-Xavier Vialard. Gromov–Wasserstein at scale, be- yond squared norms. InProceedings of the 43rd International Conference on Machine Learning, volume 306 ofProceedings of Machine Learning Research, pages 44275–44311. PMLR, 2026

View on Pith 2026
[17]

Daniel Kuhn, Soroosh Shafiee, and Wolfram Wiesemann. Distributionally robust optimization. Acta Numerica, 34:579–804, 2025

View on Pith 2025
[18]

Thomas Lam and Alexander Postnikov. Alcoved polytopes, I.Discrete & Computational Geometry, 38(3):453–478, 2007

View on Pith 2007
[19]

Facundo M´ emoli. Gromov–Wasserstein distances and the metric approach to object matching. Foundations of Computational Mathematics, 11(4):417–487, 2011

View on Pith 2011
[20]

Peyman Mohajerin Esfahani and Daniel Kuhn. Data-driven distributionally robust optimiza- tion using the Wasserstein metric: Performance guarantees and tractable reformulations.Math- ematical Programming, 171(1–2):115–166, 2018

View on Pith 2018
[21]

MOSEK ApS.MOSEK Documentation. 22

View on Pith
[22]

Brendan O’Donoghue.SCS: Splitting Conic Solver

View on Pith
[23]

Panos M. Pardalos and Stephen A. Vavasis. Quadratic programming with one negative eigen- value is NP-hard.Journal of Global Optimization, 1:15–22, 1991

View on Pith 1991
[24]

Gabriel Peyr´ e, Marco Cuturi, and Justin Solomon. Gromov–Wasserstein averaging of ker- nel and distance matrices. InProceedings of the 33rd International Conference on Machine Learning, volume 48 ofProceedings of Machine Learning Research, pages 2664–2672. PMLR, 2016

View on Pith 2016
[25]

R. Tyrrell Rockafellar and Stanislav Uryasev. Optimization of conditional value-at-risk.Jour- nal of Risk, 2(3):21–41, 2000

View on Pith 2000
[26]

R. Tyrrell Rockafellar and Stanislav Uryasev. Conditional value-at-risk for general loss distri- butions.Journal of Banking & Finance, 26(7):1443–1471, 2002

View on Pith 2002
[27]

Jayoung Ryu, Charlotte Bunne, Luca Pinello, Aviv Regev, and Romain Lopez. Cross-modality matching and prediction of perturbation responses with labeled Gromov–Wasserstein optimal transport. InProceedings of the 28th International Conference on Artificial Intelligence and Statistics, volume 258 ofProceedings of Machine Learning Research, pages 4258–4266. P...

View on Pith 2025
[28]

Shiori Sagawa, Pang Wei Koh, Tatsunori B. Hashimoto, and Percy Liang. Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case generalization. InInternational Conference on Learning Representations, 2020

View on Pith 2020
[29]

Herbert Scarf. A min-max solution of an inventory problem. InStudies in the Mathematical Theory of Inventory and Production, pages 201–209. Stanford University Press, 1958

View on Pith 1958
[30]

Soroosh Shafieezadeh-Abadeh, Daniel Kuhn, and Peyman Mohajerin Esfahani. Regularization via mass transportation.Journal of Machine Learning Research, 20(103):1–68, 2019

View on Pith 2019
[31]

Alexander Shapiro, Darinka Dentcheva, and Andrzej Ruszczy´ nski.Lectures on Stochastic Programming: Modeling and Theory. MOS-SIAM Series on Optimization. SIAM, Philadelphia, PA, second edition, 2014

View on Pith 2014
[32]

Naum Z. Shor. Quadratic optimization problems.Soviet Journal of Computer and Systems Sciences, 25(6):1–11, 1987

View on Pith 1987
[33]

Justin Solomon, Gabriel Peyr´ e, Vladimir G. Kim, and Suvrit Sra. Entropic metric alignment for correspondence problems.ACM Transactions on Graphics, 35(4):72:1–72:13, 2016

View on Pith 2016
[34]

Hoang Anh Tran, Binh Tuan Nguyen, and Yong Sheng Soh. Sum-of-Squares Hierarchy for the Gromov–Wasserstein Problem.SIAM Journal on Optimization, 36(2), 2026

View on Pith 2026
[35]

Titouan Vayer, Laetitia Chapel, R´ emi Flamary, Romain Tavenard, and Nicolas Courty. Op- timal transport for structured data with application on graphs. InProceedings of the 36th International Conference on Machine Learning, volume 97 ofProceedings of Machine Learn- ing Research, pages 6275–6284. PMLR, 2019

View on Pith 2019
[36]

C´ edric Vincent-Cuaz, R´ emi Flamary, Marco Corneli, Titouan Vayer, and Nicolas Courty. Semi-relaxed Gromov–Wasserstein divergence with applications on graphs. InInternational Conference on Learning Representations, 2022. 23

View on Pith 2022
[37]

C´ edric Vincent-Cuaz, R´ emi Flamary, Marco Corneli, Titouan Vayer, and Nicolas Courty. Template based graph neural network with optimal transport distances. InAdvances in Neural Information Processing Systems, volume 35, pages 11800–11814, 2022

View on Pith 2022
[38]

C´ edric Vincent-Cuaz, Titouan Vayer, R´ emi Flamary, Marco Corneli, and Nicolas Courty. Online graph dictionary learning. InProceedings of the 38th International Conference on Machine Learning, volume 139 ofProceedings of Machine Learning Research, pages 10564– 10574. PMLR, 2021

View on Pith 2021
[39]

Cheng Wang, Rui Gao, Feng Qiu, Jianhui Wang, and Linwei Xin. Risk-based distributionally robust optimal power flow with dynamic line rating.IEEE Transactions on Power Systems, 33(6):6074–6086, 2018

View on Pith 2018
[40]

Hongteng Xu, Dixin Luo, Hongyuan Zha, and Lawrence Carin. Gromov–Wasserstein learning for graph matching and node embedding. InProceedings of the 36th International Conference on Machine Learning, volume 97 ofProceedings of Machine Learning Research, pages 6932–

View on Pith
[41]

Yuguang Yan, Wen Li, Hanrui Wu, Huaqing Min, Mingkui Tan, and Qingyao Wu. Semi- supervised optimal transport for heterogeneous domain adaptation. InProceedings of the 27th International Joint Conference on Artificial Intelligence, pages 2969–2975. International Joint Conferences on Artificial Intelligence Organization, 2018

View on Pith 2018
[42]

Luhao Zhang, Jincheng Yang, and Rui Gao. Optimal robust policy for feature-based newsven- dor.Management Science, 70(4):2315–2329, 2024

View on Pith 2024
[43]

Shixiang Zhu, Liyan Xie, Minghe Zhang, Rui Gao, and Yao Xie. Distributionally robust weightedk-nearest neighbors. InAdvances in Neural Information Processing Systems, vol- ume 35, pages 29088–29100, 2022. 24 A Proofs A.1 Proofs for Section 2 Proof of Proposition 2.1.It suffices to show that the GW ambiguity set at radiusρ min(bµY ) contains onlybµsrGWX . ...

View on Pith 2022

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.

[1] [1]

David Alvarez-Melis and Tommi Jaakkola. Gromov–Wasserstein alignment of word embedding spaces. InProceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 1881–1890. Association for Computational Linguistics, 2018

View on Pith 2018

[2] [2]

Barbara Anthony, Vineet Goyal, Anupam Gupta, and Viswanath Nagarajan. A plant location guide for the unsure: Approximation algorithms for min-max location problems.Mathematics of Operations Research, 35(1):79–101, 2010

View on Pith 2010

[3] [3]

Immanuel M. Bomze and Etienne de Klerk. Solving standard quadratic optimization prob- lems via linear, semidefinite and copositive programming.Journal of Global Optimization, 24(2):163–185, 2002

View on Pith 2002

[4] [4]

Jon M. Borwein and Henry Wolkowicz. Facial reduction for a cone-convex programming problem.Journal of the Australian Mathematical Society, 30(3):369–380, 1981

View on Pith 1981

[5] [5]

Jens Breitung, Timo Gervens, and Julius P¨ orzgen. Graph distortion distances, gro- mov–hausdorff and the hardness of gromov–wasserstein.arXiv preprint arXiv:2610.16926, 2026

View on Pith Pith review arXiv 2026

[6] [6]

Kai Cao, Yiguang Hong, and Lin Wan. Manifold alignment for heterogeneous single-cell multi- omics data integration using Pamona.Bioinformatics, 38(1):211–219, 2022. 21

View on Pith 2022

[7] [7]

Junyu Chen, Binh T. Nguyen, Shang Hui Koh, and Yong Sheng Soh. Semidefinite relaxations of the Gromov–Wasserstein distance. InAdvances in Neural Information Processing Systems, volume 37, 2024

View on Pith 2024

[8] [8]

Liqun Chen, Zhe Gan, Yu Cheng, Linjie Li, Lawrence Carin, and Jingjing Liu. Graph optimal transport for cross-domain alignment. InProceedings of the 37th International Conference on Machine Learning, volume 119 ofProceedings of Machine Learning Research, pages 1542–1553. PMLR, 2020

View on Pith 2020

[9] [9]

Erick Delage and Yinyu Ye. Distributionally robust optimization under moment uncertainty with application to data-driven problems.Operations Research, 58(3):595–612, 2010

View on Pith 2010

[10] [10]

Pinar Demetci, Rebecca Santorella, Bj¨ orn Sandstede, William Stafford Noble, and Ritamb- hara Singh. SCOT: Single-cell multi-omics alignment with optimal transport.Journal of Computational Biology, 29(1):3–18, 2022

View on Pith 2022

[11] [11]

Pinar Demetci, Quang Huy Tran, Ievgen Redko, and Ritambhara Singh. Breaking isometric ties and introducing priors in Gromov–Wasserstein distances. InProceedings of the 27th In- ternational Conference on Artificial Intelligence and Statistics, volume 238 ofProceedings of Machine Learning Research, pages 298–306. PMLR, 2024

View on Pith 2024

[12] [12]

Rui Gao, Liyan Xie, Yao Xie, and Huan Xu. Robust hypothesis testing using Wasserstein uncertainty sets. InAdvances in Neural Information Processing Systems, volume 31, pages 7902–7912, 2018

View on Pith 2018

[13] [13]

Anupam Gupta, Benjamin Moseley, and Rudy Zhou. Structural iterative rounding for gener- alizedk-median problems.Mathematical Programming, 212:581–634, 2025

View on Pith 2025

[14] [14]

Gurobi Optimization, LLC.Gurobi Optimizer Reference Manual

View on Pith

[15] [15]

Di Hou, Tianyun Tang, and Kim-Chuan Toh. RiNNAL+: A Riemannian ALM solver for SDP-RLT relaxations of mixed-binary quadratic programs.arXiv preprint arXiv:2507.13776, 2025

View on Pith Pith review arXiv 2025

[16] [16]

Guillaume Houry, Jean Feydy, and Fran¸ cois-Xavier Vialard. Gromov–Wasserstein at scale, be- yond squared norms. InProceedings of the 43rd International Conference on Machine Learning, volume 306 ofProceedings of Machine Learning Research, pages 44275–44311. PMLR, 2026

View on Pith 2026

[17] [17]

Daniel Kuhn, Soroosh Shafiee, and Wolfram Wiesemann. Distributionally robust optimization. Acta Numerica, 34:579–804, 2025

View on Pith 2025

[18] [18]

Thomas Lam and Alexander Postnikov. Alcoved polytopes, I.Discrete & Computational Geometry, 38(3):453–478, 2007

View on Pith 2007

[19] [19]

Facundo M´ emoli. Gromov–Wasserstein distances and the metric approach to object matching. Foundations of Computational Mathematics, 11(4):417–487, 2011

View on Pith 2011

[20] [20]

Peyman Mohajerin Esfahani and Daniel Kuhn. Data-driven distributionally robust optimiza- tion using the Wasserstein metric: Performance guarantees and tractable reformulations.Math- ematical Programming, 171(1–2):115–166, 2018

View on Pith 2018

[21] [21]

MOSEK ApS.MOSEK Documentation. 22

View on Pith

[22] [22]

Brendan O’Donoghue.SCS: Splitting Conic Solver

View on Pith

[23] [23]

Panos M. Pardalos and Stephen A. Vavasis. Quadratic programming with one negative eigen- value is NP-hard.Journal of Global Optimization, 1:15–22, 1991

View on Pith 1991

[24] [24]

Gabriel Peyr´ e, Marco Cuturi, and Justin Solomon. Gromov–Wasserstein averaging of ker- nel and distance matrices. InProceedings of the 33rd International Conference on Machine Learning, volume 48 ofProceedings of Machine Learning Research, pages 2664–2672. PMLR, 2016

View on Pith 2016

[25] [25]

R. Tyrrell Rockafellar and Stanislav Uryasev. Optimization of conditional value-at-risk.Jour- nal of Risk, 2(3):21–41, 2000

View on Pith 2000

[26] [26]

R. Tyrrell Rockafellar and Stanislav Uryasev. Conditional value-at-risk for general loss distri- butions.Journal of Banking & Finance, 26(7):1443–1471, 2002

View on Pith 2002

[27] [27]

Jayoung Ryu, Charlotte Bunne, Luca Pinello, Aviv Regev, and Romain Lopez. Cross-modality matching and prediction of perturbation responses with labeled Gromov–Wasserstein optimal transport. InProceedings of the 28th International Conference on Artificial Intelligence and Statistics, volume 258 ofProceedings of Machine Learning Research, pages 4258–4266. P...

View on Pith 2025

[28] [28]

Shiori Sagawa, Pang Wei Koh, Tatsunori B. Hashimoto, and Percy Liang. Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case generalization. InInternational Conference on Learning Representations, 2020

View on Pith 2020

[29] [29]

Herbert Scarf. A min-max solution of an inventory problem. InStudies in the Mathematical Theory of Inventory and Production, pages 201–209. Stanford University Press, 1958

View on Pith 1958

[30] [30]

Soroosh Shafieezadeh-Abadeh, Daniel Kuhn, and Peyman Mohajerin Esfahani. Regularization via mass transportation.Journal of Machine Learning Research, 20(103):1–68, 2019

View on Pith 2019

[31] [31]

Alexander Shapiro, Darinka Dentcheva, and Andrzej Ruszczy´ nski.Lectures on Stochastic Programming: Modeling and Theory. MOS-SIAM Series on Optimization. SIAM, Philadelphia, PA, second edition, 2014

View on Pith 2014

[32] [32]

Naum Z. Shor. Quadratic optimization problems.Soviet Journal of Computer and Systems Sciences, 25(6):1–11, 1987

View on Pith 1987

[33] [33]

Justin Solomon, Gabriel Peyr´ e, Vladimir G. Kim, and Suvrit Sra. Entropic metric alignment for correspondence problems.ACM Transactions on Graphics, 35(4):72:1–72:13, 2016

View on Pith 2016

[34] [34]

Hoang Anh Tran, Binh Tuan Nguyen, and Yong Sheng Soh. Sum-of-Squares Hierarchy for the Gromov–Wasserstein Problem.SIAM Journal on Optimization, 36(2), 2026

View on Pith 2026

[35] [35]

Titouan Vayer, Laetitia Chapel, R´ emi Flamary, Romain Tavenard, and Nicolas Courty. Op- timal transport for structured data with application on graphs. InProceedings of the 36th International Conference on Machine Learning, volume 97 ofProceedings of Machine Learn- ing Research, pages 6275–6284. PMLR, 2019

View on Pith 2019

[36] [36]

C´ edric Vincent-Cuaz, R´ emi Flamary, Marco Corneli, Titouan Vayer, and Nicolas Courty. Semi-relaxed Gromov–Wasserstein divergence with applications on graphs. InInternational Conference on Learning Representations, 2022. 23

View on Pith 2022

[37] [37]

C´ edric Vincent-Cuaz, R´ emi Flamary, Marco Corneli, Titouan Vayer, and Nicolas Courty. Template based graph neural network with optimal transport distances. InAdvances in Neural Information Processing Systems, volume 35, pages 11800–11814, 2022

View on Pith 2022

[38] [38]

C´ edric Vincent-Cuaz, Titouan Vayer, R´ emi Flamary, Marco Corneli, and Nicolas Courty. Online graph dictionary learning. InProceedings of the 38th International Conference on Machine Learning, volume 139 ofProceedings of Machine Learning Research, pages 10564– 10574. PMLR, 2021

View on Pith 2021

[39] [39]

Cheng Wang, Rui Gao, Feng Qiu, Jianhui Wang, and Linwei Xin. Risk-based distributionally robust optimal power flow with dynamic line rating.IEEE Transactions on Power Systems, 33(6):6074–6086, 2018

View on Pith 2018

[40] [40]

Hongteng Xu, Dixin Luo, Hongyuan Zha, and Lawrence Carin. Gromov–Wasserstein learning for graph matching and node embedding. InProceedings of the 36th International Conference on Machine Learning, volume 97 ofProceedings of Machine Learning Research, pages 6932–

View on Pith

[41] [41]

Yuguang Yan, Wen Li, Hanrui Wu, Huaqing Min, Mingkui Tan, and Qingyao Wu. Semi- supervised optimal transport for heterogeneous domain adaptation. InProceedings of the 27th International Joint Conference on Artificial Intelligence, pages 2969–2975. International Joint Conferences on Artificial Intelligence Organization, 2018

View on Pith 2018

[42] [42]

Luhao Zhang, Jincheng Yang, and Rui Gao. Optimal robust policy for feature-based newsven- dor.Management Science, 70(4):2315–2329, 2024

View on Pith 2024

[43] [43]

Shixiang Zhu, Liyan Xie, Minghe Zhang, Rui Gao, and Yao Xie. Distributionally robust weightedk-nearest neighbors. InAdvances in Neural Information Processing Systems, vol- ume 35, pages 29088–29100, 2022. 24 A Proofs A.1 Proofs for Section 2 Proof of Proposition 2.1.It suffices to show that the GW ambiguity set at radiusρ min(bµY ) contains onlybµsrGWX . ...

View on Pith 2022