A Unified Dual Method for Matching Problems
Abstract
Matching problems are ubiquitous in data science as they enable the alignment of structured objects and distributions. While existing solvers are often tailored to specific matching formulations, we unify a broad class of such problems within a common mathematical and optimization framework based on duality theory. Theoretically, we demonstrate that matching objectives decomposable as a difference of convex (DC) functions can be recast as implicit registration problems. This connection links matching to another well-studied class of objectives and yields a dual formulation amenable to natural optimization strategies. We then apply these findings to quadratic matching (QM) problems, which admit DC decompositions and for which we provide extensive convergence guarantees. Our framework applies to Gromov-Wasserstein (GW), as well as its unbalanced formulation and several variants, which are increasingly popular QM problems. Numerically, we implement our algorithms at scale for various data modalities such as graphs, point clouds, meshes, and word embeddings. Finally, our modular approach allows us to explore new formulations such as fracture matching, broadening the scope of problems that can be addressed within this framework..
Related
- A Unified Framework for Assortment Optimization and Matching under MNL Choice
- UniFlow: Unified Multi-Scale Flow Matching for Time Series Generation
- Reconstruction-Aware Distribution Matching for Inverse Problems with Unpaired Data
- Flow Matching for Fast Posterior Sampling in Bayesian Inverse Problems
- Physics-Guided Conditional Flow Matching with Energy Regularization for Robust PDE Inverse Problems
BibTeX
@misc{houry2026unified,
title = {{A Unified Dual Method for Matching Problems}},
author = {Guillaume Houry and Ferdinand Genans and Jean Feydy and François-Xavier Vialard},
howpublished = {HAL},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.39339},
eprint = {2609.39339},
archivePrefix = {arXiv},
url = {https://hal.science/hal-05768666v1},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A Unified Dual Method for Matching Problems
AU - Guillaume Houry
AU - Ferdinand Genans
AU - Jean Feydy
AU - François-Xavier Vialard
PY - 2026
DA - 2026/09/30
PB - HAL
DO - 10.48550/arxiv.2609.39339
UR - https://hal.science/hal-05768666v1
AB - Matching problems are ubiquitous in data science as they enable the alignment of structured objects and distributions. While existing solvers are often tailored to specific matching formulations, we unify a broad class of such problems within a common mathematical and optimization framework based on duality theory. Theoretically, we demonstrate that matching objectives decomposable as a difference of convex (DC) functions can be recast as implicit registration problems. This connection links matching to another well-studied class of objectives and yields a dual formulation amenable to natural optimization strategies. We then apply these findings to quadratic matching (QM) problems, which admit DC decompositions and for which we provide extensive convergence guarantees. Our framework applies to Gromov-Wasserstein (GW), as well as its unbalanced formulation and several variants, which are increasingly popular QM problems. Numerically, we implement our algorithms at scale for various data modalities such as graphs, point clouds, meshes, and word embeddings. Finally, our modular approach allows us to explore new formulations such as fracture matching, broadening the scope of problems that can be addressed within this framework..
ER -