← List all talks ...

Gromov-Wasserstein Distances: Entropic Regularization, Duality, and Sample Complexity

Ziv Goldfeld – Assistant Professor, Cornell University

Thu, 23-Feb-2023 / 4:00pm / Packard 202

Abstract

The Gromov-Wasserstein (GW) distance quantifies dissimilarity between metric measure spaces and provides a natural correspondence between them. As such, it serves as a figure of merit for applications involving alignment of heterogeneous datasets, including object matching, multi-modal analysis of biological data, matching language models, and many more. While computational aspects of the GW distance have been widely studied, a duality theory and foundational statistical questions concerning empirical convergence rates remained open. This work closes these gaps for the GW distance with quadratic cost over Euclidean spaces of different dimensions d_x and d_y. We consider both the standard GW and the entropic GW (EGW) distances, derive dual formulations thereof, and use them to analyze expected empirical convergence rates. The resulting rates are n^{-2/\max{d_x,d_y,4}} (up to a log factor when \max{d_x,d_y}=4) and n^{-¹⁄₂} for the two-sample GW and EGW problems, respectively, which match the corresponding rates for standard and entropic optimal transport. Our results serve as a first step towards a comprehensive statistical theory as well as computational advancements for GW distances, based on the discovered dual formulation.

Bio

Ziv Goldfeld is an assistant professor in the School of Electrical and Computer Engineering, and a graduate field member in Computer Science, Statistics, Data Science, and the Center of Applied Mathematics, at Cornell University. Before joining Cornell, he was a postdoctoral research fellow in LIDS at MIT. Ziv graduated with a B.Sc., M.Sc., and Ph.D. (all summa cum laude) in Electrical and Computer Engineering from Ben Gurion University, Israel. Ziv’s research interests include optimal transport theory, statistical learning theory, information theory, and mathematical statistics. Honors include the NSF CAREER Award, the IBM University Award, and the Rothschild Postdoctoral Fellowship.